TY - RPRT
T1 - Space sweep solves intersection of two convex polyhedra elegantly
T3 - Saarbrücken, 1984
A1 - Hertel,Stefan
A1 - Mehlhorn,Kurt
A1 - Mäntylä,Martti
A1 - Nievergelt,Jurg
Y1 - 2011/09/02
N2 - 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.
CY - Saarbrücken
PB - Saarländische Universitäts- und Landesbibliothek
AD - Postfach 151141, 66041 Saarbrücken
UR - http://scidok.sulb.uni-saarland.de/volltexte/2011/4145
ER -