A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

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

Abstract

Chazelle [FOCS 89] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

Original languageEnglish (US)
Title of host publication31st International Symposium on Computational Geometry, SoCG 2015
EditorsJanos Pach, Janos Pach, Lars Arge
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages733-738
Number of pages6
ISBN (Electronic)9783939897835
DOIs
StatePublished - Jun 1 2015
Externally publishedYes
Event31st International Symposium on Computational Geometry, SoCG 2015 - Eindhoven, Netherlands
Duration: Jun 22 2015Jun 25 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume34
ISSN (Print)1868-8969

Other

Other31st International Symposium on Computational Geometry, SoCG 2015
CountryNetherlands
CityEindhoven
Period6/22/156/25/15

Keywords

  • Convex polyhedra
  • Dobkin Kirkpatrick hierarchy
  • Intersection

ASJC Scopus subject areas

  • Software

Cite this