TY - GEN

T1 - On translational motion planning in 3-space

AU - Aronov, Boris

AU - Sharir, Micha

PY - 1994

Y1 - 1994

N2 - Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,....,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi Ai ⊕ (-B), for i = l,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log2 k), where n is the total complexity of the individual Minkowski sums P1,..., Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log3 k).

AB - Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,....,Ak with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski sums Pi Ai ⊕ (-B), for i = l,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log2 k), where n is the total complexity of the individual Minkowski sums P1,..., Pk. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log3 k).

UR - http://www.scopus.com/inward/record.url?scp=0028015213&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028015213&partnerID=8YFLogxK

U2 - 10.1145/177424.177445

DO - 10.1145/177424.177445

M3 - Conference contribution

AN - SCOPUS:0028015213

SN - 0897916484

SN - 9780897916486

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 21

EP - 30

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Publ by ACM

T2 - Proceedings of the 10th Annual Symposium on Computational Geometry

Y2 - 6 June 1994 through 8 June 1994

ER -