非表示:
キーワード:
-
要旨:
Summary Plane-sweep algorithms form a fairly general approach to
two-dimensional problems of computational geometry. No corresponding general
space-sweep algorithms for geometric problems in 3- space are known. We derive
concepts for such space-sweep algorithms that yield an efficient solution to
the problem of solving any set operation (union, intersection, ...) of two
convex polyhedra. Our solution matches the best known time bound of O(n log n),
where n is the combined number of vertices of the two polyhedra.
