## Abstract

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A_{1},..., A_{k} 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 P_{i} = A_{i} ⊕ (-B), for i = 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and that it can be Ω(nkα(k)) in the worst case, where n is the total complexity of the individual Minkowski sums P_{1},...,P_{k}. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log k log n).

Original language | English (US) |
---|---|

Pages (from-to) | 1785-1803 |

Number of pages | 19 |

Journal | SIAM Journal on Computing |

Volume | 26 |

Issue number | 6 |

DOIs | |

State | Published - Dec 1997 |

## Keywords

- Algorithmic motion planning
- Combinatorial complexity
- Combinatorial geometry
- Computational geometry
- Convex polyhedra
- Geometric algorithms
- Randomized algorithms

## ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)