### 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

## Fingerprint Dive into the research topics of 'A linear algorithm for determining the separation of convex polyhedra'. Together they form a unique fingerprint.

## Cite this

Dobkin, D. P., & Kirkpatrick, D. G. (1985). A linear algorithm for determining the separation of convex polyhedra.

*Journal of Algorithms*,*6*(3), 381-392. https://doi.org/10.1016/0196-6774(85)90007-0