Union of fat objects in three dimensions
An object in $\mathbb{R}^3$ is called fat if the ratio of its circumradius to its inradius is bounded by a constant.
Agarwal and Sharir bounded by $O(n^{2+\varepsilon})$ the complexity of the union of the Minkowski sums of polyhedra having $n$ vertices in total with the Euclidean unit ball, and Pach, Safruti and Sharir proved the same bound for the union of $n$ congruent cubes. Efrat and Sharir proved the analogous result for fat objects in the plane.
Problem. For $n$ fat objects in $\mathbb{R}^3$, what is the combinatorial complexity of their union?
Source: Origin uncertain; Problem 4 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- fat objects, The Open Problems Project, union complexity
References
@inproceedings{agarwal1999,
author = {Agarwal, Pankaj K. and Sharir, Micha},
title = {Pipes, cigars, and kreplach: The union of {M}inkowski sums in three dimensions},
booktitle = {Proc. 15th Annu. ACM Sympos. Comput. Geom.},
year = {1999},
pages = {143--153},
}
@inproceedings{pach2001,
author = {Pach, J{\'a}nos and Safruti, Ido and Sharir, Micha},
title = {The union of congruent cubes in three dimensions},
booktitle = {Proc. 17th Annu. ACM Sympos. Comput. Geom.},
year = {2001},
pages = {19--28},
}
@article{efrat2000,
author = {Efrat, A. and Sharir, Micha},
title = {On the complexity of the union of fat objects in the plane},
journal = {Discrete Comput. Geom.},
volume = {23},
year = {2000},
pages = {171--189},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01069, "Union of fat objects in three dimensions", clopen.solutions.