Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

Timothy M. Chan, Konstantinos Tsakalidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matou ek (1992) and the optimal but randomized algorithm of Ramos (1999). This leads to efficient derandomization of previous algorithms for numerous wellstudied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (≤ κ)-levels in 3-d, order-κ Voronoi diagrams in 2-d, linear programming with κ violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, ε-nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matou ek (1991) and Chazelle (1993).

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages719-732
Number of pages14
ISBN (Electronic)9783939897835
DOIs
StatePublished - Jun 1 2015
Externally publishedYes
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume34
ISSN (Print)1868-8969

Other

Other31st International Symposium on Computational Geometry, SoCG 2015
CountryNetherlands
CityEindhoven
Period6/22/156/25/15

Keywords

  • Derandomization
  • Geometric data structures
  • Halfspace range reporting
  • Shallow cuttings

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings'. Together they form a unique fingerprint.

Cite this