An optimal algorithm for intersecting three-dimensional convex polyhedra
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 586-591
- https://doi.org/10.1109/sfcs.1989.63539
Abstract
A linear algorithm for intersecting two convex polyhedra in 3-space is described. The algorithm is quite simple; it does not require any complicated data structure and should be practical. A number of optimal algorithms for other problems are obtained directly from this result. These include intersecting several polytopes at once or computing the convex hull of their union, merging Voronoi diagrams in the plane in linear time, and computing three-dimensional convex hulls in linear expected time.Keywords
This publication has 15 references indexed in Scilit:
- Primitives for the manipulation of three-dimensional subdivisionsPublished by Association for Computing Machinery (ACM) ,1987
- Intersection of convex objects in two and three dimensionsJournal of the ACM, 1987
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Space sweep solves intersection of convex polyhedraActa Informatica, 1984
- Fast detection of polyhedral intersectionTheoretical Computer Science, 1983
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983
- Efficient computation of continuous skeletonsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Finding the intersection of two convex polyhedraTheoretical Computer Science, 1978