**Next:** Problem 5: Euclidean Minimum Spanning Tree

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

- Statement
What is the complexity of the union of “fat” objects in \R^3?

- Origin
Uncertain, pending investigation.

- Status/Conjectures
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].- Appearances
- Categories
combinatorial geometry

- Entry Revision History
J. O’Rourke, 1 Aug. 2001; 1 Jan. 2003 (B. Aronov comment).

- [AS99]
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.- [ES00]
A. Efrat and Micha Sharir. On the complexity of the union of fat objects in the plane.

*Discrete Comput. Geom.*, 23:171–189, 2000.- [MO01]
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.- [PSS01]
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.