## Abstract

The separation of two convex polyhedra is defined to be the minimum distance from a point (not necessarily an extreme point) of one to a point of the other. A linear time algorithm is presented for constructing a pair of points that realize the separation of two convex polyhedra in three dimensions. This algorithm is based on a simple hierarchical description of polyhedra that is of interest in its own right. The result provides a linear algorithm for detecting the intersection of convex polyhedra. Separation and intersection detection algorithms have applications in clustering, the intersection of half-spaces, linear programming, and robotics.

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

Pages (from-to) | 381-392 |

Number of pages | 12 |

Journal | Journal of Algorithms |

Volume | 6 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1985 |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics