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
- Uncertain, pending investigation.
Conjectured to be nearly quadratic.
- Partial and Related Results
- The Minkowski sum of polyhedra of n vertices
with the (Euclidean) unit ball
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
- 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
In Proc. 15th Annu. ACM Sympos. Comput. Geom., pages 143-153,
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,
The Open Problems Project - December 04, 2015