An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
- 1 August 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (4) , 671-696
- https://doi.org/10.1137/0221041
Abstract
This paper describes a linear-time algorithm for computing the intersection of two convex polyhedra in 3-space. Applications of this result to computing intersections, convex hulls, and Voronoi diagrams are also given.Keywords
This publication has 18 references indexed in Scilit:
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- Intersection of convex objects in two and three dimensionsJournal of the ACM, 1987
- Voronoi diagrams and arrangementsDiscrete & Computational Geometry, 1986
- Efficient uses of the pastJournal of Algorithms, 1985
- A linear algorithm for determining the separation of convex polyhedraJournal of Algorithms, 1985
- Finding extreme points in three dimensions and solving the post-office problem in the planeInformation Processing Letters, 1985
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Linear Time Algorithms for Two- and Three-Variable Linear ProgramsSIAM Journal on Computing, 1984
- Fast detection of polyhedral intersectionTheoretical Computer Science, 1983
- Divide and conquer for linear expected timeInformation Processing Letters, 1978