### 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 = l,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log^{2} k), where n is the total complexity of the individual Minkowski sums P_{1},..., P_{k}. 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 log^{3} k).

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

Title of host publication | Proceedings of the Annual Symposium on Computational Geometry |

Publisher | Publ by ACM |

Pages | 21-30 |

Number of pages | 10 |

ISBN (Print) | 0897916484, 9780897916486 |

DOIs | |

State | Published - 1994 |

Event | Proceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA Duration: Jun 6 1994 → Jun 8 1994 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | Proceedings of the 10th Annual Symposium on Computational Geometry |
---|---|

City | Stony Brook, NY, USA |

Period | 6/6/94 → 6/8/94 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'On translational motion planning in 3-space'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Annual Symposium on Computational Geometry*(pp. 21-30). (Proceedings of the Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/177424.177445