Next: Problem 5: Euclidean Minimum Spanning Tree
Previous: Problem 3: Voronoi Diagram of Lines in 3D
What is the complexity of the union of “fat” objects in \R^3?
Uncertain, pending investigation.
Open. Conjectured to be nearly quadratic.
The Minkowski sum of polyhedra of n vertices with the (Euclidean) unit ball has complexity O(n^{2+\epsilon}) [AS99], as does the union of n congruent cubes [PSS01]. It is widely believed the same should hold true for fat objects, those with a bounded ratio of circumradius to inradius, as it does in \R^2 [ES00].
combinatorial geometry
J. O’Rourke, 1 Aug. 2001; 1 Jan. 2003 (B. Aronov comment).
Pankaj K. Agarwal and Micha Sharir. Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions. In Proc. 15th Annu. ACM Sympos. Comput. Geom., pages 143–153, 1999.
A. Efrat and Micha Sharir. On the complexity of the union of fat objects in the plane. Discrete Comput. Geom., 23:171–189, 2000.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.
Janos Pach, Ido Safruit, and Micha Sharir. The union of congruent cubes in three dimensions. In Proc. 17th Annu. ACM Sympos. Comput. Geom., pages 19–28, 2001.