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

Timothy M. Chan, Konstantinos Tsakalidis

Research output: Contribution to journalArticlepeer-review


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 (Comput Geom 2(3):169–186, 1992) and the optimal but randomized algorithm of Ramos (Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG’99, 1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (≤ k) -levels in 3-d, order-k Voronoi diagrams in 2-d, linear programming with k 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 (Discrete Comput Geom 6(1):385–406, 1991) and Chazelle (Discrete Comput Geom 9(1):145–158, 1993).

Original languageEnglish (US)
Pages (from-to)866-881
Number of pages16
JournalDiscrete and Computational Geometry
Issue number4
StatePublished - Dec 1 2016
Externally publishedYes


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


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