Please use this identifier to cite or link to this item: doi:10.22028/D291-26109
Title: Space sweep solves intersection of two convex polyhedra elegantly
Author(s): Hertel, Stefan
Mehlhorn, Kurt
Mäntylä, Martti
Nievergelt, Jurg
Language: English
Year of Publication: 1984
OPUS Source: Saarbrücken, 1984
Free key words: computational geometry
sweep algorithms
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: Plane-sweep algorithms form a fairly general approach to two-dimensional problems of computational geometry. No corresponding three-dimensional space-sweep algorithms for geometric problems in 3-space are known, however. We derive concepts for such space-sweep algorithms that yield an elegant solution to the problem of solving any set operation (union, intersection, ...) of two convex polyhedra. Moreover, our solution matches the best known time bound of O(n log n) where n is the combined number of corners of the two polyhedra.
Link to this record: urn:nbn:de:bsz:291-scidok-41454
Series name: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Series volume: 1984/02
Date of registration: 2-Sep-2011
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1984_02.pdf9,03 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.