An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra

Report ID: TR-205-89

---

Author: Chazelle, Bernard

---

Date: 1989-02-00

---

Pages: 30

---

Download Formats: |PDF|

---

Abstract:

We describe a linear-time algorithm for computing the intersection of two convex polyhedra in 3-space. Applications of this result to computing intersections, convex hulls, and Voronoi diagrams are given.