Document Open Access Logo

An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D

Authors Pankaj K. Agarwal, Alex Steiger

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.10.pdf
  • Filesize: 1.34 MB
  • 20 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Department of Computer Science, Duke University, Durham, NC, USA
Alex Steiger
  • Department of Computer Science, Duke University, Durham, NC, USA

Funding

Partially supported by NSF grants IIS-18-14493 and CCF-20-07556.

Cite As Get BibTex

Pankaj K. Agarwal and Alex Steiger. An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.10

Abstract

Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ³. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n²). We show that U can be computed in O(n log³ n + κ) time if C is in general position. The algorithm also computes the union of a set of fat boxes (i.e., boxes with bounded aspect ratio) within the same time bound. If the cubes in C are congruent or have bounded depth, the running time improves to O(n log² n), and if both conditions hold, the running time improves to O(n log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • union of cubes
  • fat boxes
  • plane-sweep

Metrics

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

References

  1. Pankaj K. Agarwal. An improved algorithm for computing the volume of the union of cubes. In Proc. 26th Annu. Sympos. Comp. Geom., pages 230-239. ACM, 2010. Google Scholar
  2. Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Computing the volume of the union of cubes. In Proc. 23rd Annu. Sympos. Comp. Geom., pages 294-301. ACM, 2007. Google Scholar
  3. Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Union of hypercubes and 3d minkowski sums with random sizes. Discret. Comput. Geom., 65(4):1136-1165, 2021. Google Scholar
  4. Pankaj K. Agarwal, Micha Sharir, and Alex Steiger. Decomposing the complement of the union of cubes in three dimensions. In Proc. 2021 ACM-SIAM Sympos. Disc. Alg., pages 1425-1444. SIAM, 2021. Google Scholar
  5. Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM, 45(6):891-923, 1998. Google Scholar
  6. Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discret. Comput. Geom., 19(4):485-519, 1998. Google Scholar
  7. Karl Bringmann. An improved algorithm for Klee’s measure problem on fat boxes. Comput. Geom., 45(5-6):225-233, 2012. Google Scholar
  8. Timothy M. Chan. Klee’s measure problem made easy. In Proc. 54th Annu. IEEE Sympos. Found. Comp. Sci., pages 410-419. IEEE Computer Society, 2013. Google Scholar
  9. L. Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem. Geometric pattern matching in d-dimensional space. Discret. Comput. Geom., 21(2):257-274, 1999. Google Scholar
  10. Herbert Edelsbrunner and Ernst P. Mücke. Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph., 9(1):66-104, 1990. Google Scholar
  11. Alon Efrat. Private communication. Google Scholar
  12. Ralf Hartmut Güting. An optimal contour algorithm for iso-oriented rectangles. J. Algorithms, 5(3):303-326, 1984. Google Scholar
  13. Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society, 2011. Google Scholar
  14. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput., 46(6):1712-1744, 2017. Google Scholar
  15. Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin. Efficient colored orthogonal range counting. SIAM J. Comput., 38(3):982-1011, 2008. Google Scholar
  16. Mark H. Overmars and Chee-Keng Yap. New upper bounds in Klee’s measure problem. SIAM J. Comput., 20(6):1034-1045, 1991. Google Scholar
  17. Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Springer, 1985. Google Scholar
  18. Derick Wood. The contour problem for rectilinear polygons. Inf. Process. Lett., 19(5):229-236, 1984. Google Scholar
  19. Hakan Yildiz and Subhash Suri. Computing Klee’s measure of grounded boxes. Algorithmica, 71(2):307-329, 2015. 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