next up previous
Next: Problem 5: Euclidean Minimum Up: The Open Problems Project Previous: Problem 3: Voronoi Diagram

Problem 4: Union of Fat Objects in 3D

What is the complexity of the union of ``fat'' objects in $ \mathbb {R}$3?
Uncertain, pending investigation.
Open. Conjectured to be nearly quadratic.
Partial and Related Results
The Minkowski sum of polyhedra of n vertices with the (Euclidean) unit ball has complexity O(n2+ε) [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 $ \mathbb {R}$2 [ES00].
combinatorial geometry
Entry Revision History
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.

The Open Problems Project - September 19, 2017