Abstract.
Let Ω be a set of pairwise-disjoint polyhedral obstacles in R 3 with a total of n vertices, and let B be a ball in R 3. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n 2+ε ), for any ε >0; the constant of proportionality depends on ε. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F . The special case in which Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n 2+ε ).
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.
Rights and permissions
About this article
Cite this article
Agarwal, P., Sharir, M. Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions. Discrete Comput Geom 24, 645–657 (2000). https://doi.org/10.1007/s004540010064
Issue Date:
DOI: https://doi.org/10.1007/s004540010064