Finding the Intersection of Two Convex Polyhedra.
Abstract
Given two convex polyhedra in three-dimensional space, we develop an algorithm to (1) test whether their intersection is empty, and (2) if so to find a separating plane, while (3) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in time 0(nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (3) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1977
- Accession Number
- ADA056889
Entities
People
- D. E. Muller
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign