Document Open Access Logo

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

Authors Timothy M. Chan, Konstantinos Tsakalidis

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.719.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Timothy M. Chan
Konstantinos Tsakalidis

Cite As Get BibTex

Timothy M. Chan and Konstantinos Tsakalidis. Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 719-732, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.719

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 Matousek (1992) and the optimal but randomized algorithm of Ramos (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, epsilon-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 Matousek (1991) and Chazelle (1993).

Subject Classification

Keywords
  • shallow cuttings
  • derandomization
  • halfspace range reporting
  • geometric data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 180-186. SIAM, 2009. Google Scholar
  2. Peyman Afshani, Timothy M. Chan, and Konstantinos Tsakalidis. Deterministic rectangle enclosure and offline dominance reporting on the RAM. In Proceedings of the Forty-First International Colloquium on Automata, Languages, and Programming, Part I, ICALP '14, pages 77-88, 2014. Google Scholar
  3. Peyman Afshani and Konstantinos Tsakalidis. Optimal deterministic shallow cuttings for 3d dominance ranges. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1389-1398. SIAM, 2014. Google Scholar
  4. Pankaj K. Agarwal. Partitioning arrangements of lines I: An efficient deterministic algorithm. Discrete & Computational Geometry, 5(1):449-483, 1990. Google Scholar
  5. Pankaj K. Agarwal. Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, New York, NY, USA, 1991. Google Scholar
  6. Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, and Micha Sharir. On levels in arrangements of lines, segments, planes, and triangles. Discrete & Computational Geometry, 19(3):315-331, 1998. Google Scholar
  7. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull with optimal query time. In Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory, SWAT '00, pages 57-70, 2000. Google Scholar
  8. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In Proceedings of the Forty-Third Symposium on Foundations of Computer Science, FOCS '02, pages 617-626. IEEE, 2002. Current draft of full paper at https://pwgrp1.inf.ethz.ch/Current/DPCH/Journal/topdown.pdf. Google Scholar
  9. Timothy M. Chan. Random sampling, halfspace range reporting, and construction of (≤ k)-levels in three dimensions. SIAM Journal on Computing, 30(2):561-575, 2000. Google Scholar
  10. Timothy M. Chan. Low-dimensional linear programming with violations. SIAM Journal on Computing, 34(4):879-893, April 2005. Google Scholar
  11. Timothy M. Chan. Three problems about dynamic convex hulls. International Journal of Computational Geometry & Applications, 22(04):341-364, 2012. Google Scholar
  12. Timothy M. Chan, Kasper Green Larsen, and Mihai Pǎtraşcu. Orthogonal range searching on the RAM, revisited. In Proceedings of the Twenty-Seventh Symposium on Computational Geometry, SOCG '11, pages 1-10. ACM, 2011. Google Scholar
  13. Timothy M. Chan and Mihai Pǎtraşcu. Transdichotomous results in computational geometry, I: point location in sublogarithmic time. SIAM J. Comput., 39(2):703-729, 2009. Google Scholar
  14. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry, 9(1):145-158, 1993. Google Scholar
  15. Bernard Chazelle and Joel Friedman. A deterministic view of random sampling and its use in geometry. Combinatorica, 10(3):229-249, 1990. Google Scholar
  16. Kenneth L. Clarkson. New applications of random sampling in computational geometry. Discrete & Computational Geometry, 2:195-222, 1987. Google Scholar
  17. Martin E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing, 13(1):31-45, 1984. Google Scholar
  18. Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16(6):1004-1022, 1987. Google Scholar
  19. Michael T. Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 51(3):374-389, 1995. Google Scholar
  20. Sariel Har-Peled, Haim Kaplan, Micha Sharir, and Shakhar Smorodinsky. Epsilon-nets for halfspaces revisited. CoRR, abs/1410.3154, 2014. Google Scholar
  21. David Haussler and Emo Welzl. ε-nets and simplex range queries. Discrete & Computational Geometry, 2(1):127-151, 1987. Google Scholar
  22. Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  23. Jiří Matoušek. Construction of ε-nets. Discrete & Computational Geometry, 5(1):427-448, 1990. Google Scholar
  24. Jiří Matoušek. Cutting hyperplane arrangements. Discrete & Computational Geometry, 6(1):385-406, 1991. Google Scholar
  25. Jiří Matoušek. Reporting points in halfspaces. Computational Geometry, 2(3):169-186, 1992. Google Scholar
  26. Jiří Matoušek. On constants for cuttings in the plane. Discrete & Computational Geometry, 20(4):427-448, 1998. Google Scholar
  27. Nimrod Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  28. Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, 1984. Google Scholar
  29. Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG '99, pages 390-399. ACM, 1999. Google Scholar
  30. Edgar A. Ramos. Deterministic algorithms for 3-d diameter and some 2-d lower envelopes. In Proceedings of the Sixteenth Annual Symposium on Computational Geometry, SoCG '00, pages 290-299. ACM, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact