Optimal algorithm for intersecting three-dimensional convex polyhedra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

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 languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages586-591
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - Jan 1 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/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