Ham-Sandwich Cuts for Abstract Order Types
OPEN ACCESS
Author / Producer
Date
2018-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
The linear-time ham-sandwich cut algorithm of Lo, Matoušek, and Steiger for bi-chromatic finite point sets in the plane works by appropriately selecting crossings of the lines in the dual line arrangement with a set of well-chosen vertical lines. We consider the setting where we are not given the coordinates of the point set, but only the orientation of each point triple (the order type) and give a deterministic linear-time algorithm for the mentioned sub-algorithm. This yields a linear-time ham-sandwich cut algorithm even in our restricted setting. We also show that our methods are applicable to abstract order types.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
80 (1)
Pages / Article No.
234 - 257
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Abstract order type; Ham-sandwich cut; Pseudo-line arrangement
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.