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

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

[MO01]

Categories

combinatorial geometry

Entry Revision History

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

Bibliography

[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.