### Abstract

A linear algorithm for intersecting two convex polyhedra in 3-space is described. The algorithm is quite simple; it does not require any complicated data structure and should be practical. A number of optimal algorithms for other problems are obtained directly from this result. These include intersecting several polytopes at once or computing the convex hull of their union, merging Voronoi diagrams in the plane in linear time, and computing three-dimensional convex hulls in linear expected time.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 586-591 |

Number of pages | 6 |

ISBN (Print) | 0818619821, 9780818619823 |

DOIs | |

State | Published - Jan 1 1989 |

Event | 30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA Duration: Oct 30 1989 → Nov 1 1989 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 30th Annual Symposium on Foundations of Computer Science |
---|---|

City | Research Triangle Park, NC, USA |

Period | 10/30/89 → 11/1/89 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Optimal algorithm for intersecting three-dimensional convex polyhedra'. Together they form a unique fingerprint.

## Cite this

Chazelle, B. (1989). Optimal algorithm for intersecting three-dimensional convex polyhedra. In

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 586-591). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1989.63539