The Open Problems Project

Next: Problem 5: Euclidean Minimum Spanning Tree

Previous: Problem 3: Voronoi Diagram of Lines in 3D

Problem 4: Union of Fat Objects in 3D


What is the complexity of the union of “fat” objects in \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(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

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.