Problem 4: Union of Fat Objects in 3D

Statement

What is the complexity of the union of ``fat'' objects in $\mathbb {R}$³?

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 $\mathbb {R}$² [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.