Union of Fat Objects in 3D

Statement:

What is the complexity of the union of “fat” objects in \( \mathbb{R}^2 \)

Author	Date Published
Uncertain, pending investigation.	Unknown

Partial Results:

The Minkowski sum of polyhedra of n vertices with the (Euclidean) unit ball has complexity \( O(n^{2+e}) \) [1], as does the union of n congruent cubes [2]. 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}^2 \)[3].

References:

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

[2]A. Efrat and Micha Sharir. On the complexity of the union of fat objects in the plane. Discrete Comput. Geom., 23:171–189, 2000.

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

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

Keywords:

Combinatorial Geometry; fat; 3D; union