Finding the Intersection of a Set of n Half-Spaces in Time O(nlogn).
Abstract
A set of n half-spaces in three-dimensional space is given and an algorithm for finding the common intersection in time O(nlogn) is developed. The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (1) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (2) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(nlogn); (3) since the half-space intersection is nonempty if and only if these two convex hulls are dispoint, a separating plane is found, also in time O(nlogn); (4) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the latter can be found in time O(n), the overall running time of the procedure is O(nlogn). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1977
- Accession Number
- ADA057560
Entities
People
- D. E. Muller
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign