Finding the Intersection of a Set of n Half-Spaces in Time O(nlogn).
F. P. Preparata, David E. Muller · Defense Technical Information Center (DTIC) · 1977
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.