Back to Search
Start Over
Ham-Sandwich Cuts for Abstract Order Types.
- Source :
-
Algorithmica . Jan2018, Vol. 80 Issue 1, p234-257. 24p. - Publication Year :
- 2018
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 80
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 127064902
- Full Text :
- https://doi.org/10.1007/s00453-016-0246-4