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

详细信息    查看全文

• 作者：Timothy M. Chan ; Konstantinos Tsakalidis
• 关键词：Shallow cuttings ; Derandomization ; Halfspace range reporting ; Geometric data structures
• 刊名：Discrete and Computational Geometry
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：56
• 期：4
• 页码：866-881
• 全文大小：566 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444
• 卷排序：56

文摘

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, \(({\le }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, \(\varepsilon \)-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).