Next: Problem 5: Euclidean Minimum
Up: The Open Problems Project
Previous: Problem 3: Voronoi Diagram
Problem 4: Union of Fat Objects in 3D
 Statement
 What is the complexity of the union of ``fat'' objects
in
^{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+ε}) [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
^{2} [ES00].
 Appearances
 [MO01]
 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 143153,
1999.
 ES00

A. Efrat and Micha Sharir.
On the complexity of the union of fat objects in the plane.
Discrete Comput. Geom., 23:171189, 2000.
 MO01

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573582, 2001.
Also in SIGACT News 32(3):6372 (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 1928,
2001.
The Open Problems Project  September 19, 2017