Space Sweep Solves Intersection of Convex Polyhedra

Hertel, Stefan; Mäntylä, Martti; Mehlhorn, Kurt; Nievergelt, Jurg

doi:10.1007/BF00271644

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Space Sweep Solves Intersection of Convex Polyhedra

MPS-Authors

Hertel, Stefan
Max Planck Society;

Mäntylä, Martti
Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Nievergelt, Jurg
Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Hertel, S., Mäntylä, M., Mehlhorn, K., & Nievergelt, J. (1984). Space Sweep Solves Intersection of Convex Polyhedra. Acta Informatica, 21, 501-519. doi:10.1007/BF00271644.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AEFD-E

Abstract

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.