\titlestuff{

}

% Reference macros

Considerable attention has been paid recently to solving linear programming problems when the number of variables (or, dually, the number of constraints) involved is small, or fixed. An $O(n \lg n)$ algorithm for the two dimensional case is implicit in the work of Shamos on computing the common intersection of $n$ half planes [\Sham]. More recently, Megiddo has obtained algorithms for linear programming that are {\it linear} in the number of constraints, for any fixed number of variables [\Megid]. Although the number of variables enters exponentially into the running time of Megiddo's algorithms, for small dimensionality his techniques may turn out to be practical, and they certainly admit of nice geometric interpretations.

In this note we will consider a variant of the linear programming problem, where the set of constraints is relatively stable, but the objective function frequently changes. This situation often arises in practice, where the constraints may correspond to fixed requirements but the objective function may be a cost that depends on fluctuating prices. The approach we take is to preprocess the constraints into a structure such that given any linear objective function, we can quickly report the point(s) in space maximizing it (this may be the point at infinity, if the solution polytope is unbounded).

We will confine our attention in the main body of the note to three dimensional constraints. Some comments about application of the same techniques to an arbitrary, but fixed, number of dimensions will be given at the end. For three dimensions, the auxiliary structure that we build can be constructed in time $O(n \lg n)$ and uses space $O(n)$. Once it is in place, the point maximizing some objective function can be determined in time $O(\lg n)$. Thoughout the discussion we will freely use standard concepts from linear programming.

As is well known, the intersection of a set of half-spaces in 3-space is a convex (but possibly empty, or unbounded) polyhedron. The half-spaces represent our constraints, and the polyhedron the set of feasible points. Our problem may be infeasible, or unbounded, according as to whether the corresponding polyhedron is empty, or unbounded. The faces of the polyhedron represent the essential constraints in our set. Certain pairs of them intersect in edges of the polyhedron, and edges in turn meet at vertices, where three or more faces also meet. It is known that any linear objective function is always maximized at a vertex of this polyhedron, if we include the point at infinity as a vertex for the unbounded case. In certain degenerate cases an entire edge, or face, may consist of points all maximizing the objective function.

The first stage of the preprocessing in our method is to compute this convex polyhedron. This problem has been solved by Preparata and Muller in time $O(n \lg n)$ [\PrepMul]. The output of any such algorithm is a data structure representing the adjacencies between the edges and the incidences between the vertices, edges, and faces of the polyhedron. Many such structures have been proposed in the literature [\Baum], but we will choose the {\it quad edge} data structure described in [\GuibStolf] because it simultaneously represents a polyhedron and its dual, a fact that we will use to advantage later on. This structure uses linear storage in the number of the original constraints. (It is worth pointing out that the number of vertices and edges in the polyhedron is each bounded by a small constant times the number of faces). Preparata and Muller's method is essentially based on the duality of the half-space intersection problem to that of determining the convex hull of $n$ points in three space. This duality is not as straighforward as it may first seem, and some of the difficulties and how they can be overcome are described in their paper.

We now proceed to construct a subdivision of the unit sphere, based on the polyhedron computed above. The subdivision will be topologically equivalent to the dual of the polyhedron. Each face of the polyhedron is mapped onto the point on the sphere where the tangent plane to sphere is parallel to the face, and has the sphere on the same side as the face has the polyhedron. Two such points on the sphere will be joined by a great circle arc, if and only if the corresponding faces of the polyhedron are adjacent. To be precise, we always use the arc that is less than $\pi$. This construction can be carried out in linear time by a traversal of the quad edge data structure representing the polyhedron. In this traversal, as each dual vertex is being visited, the corresponding point on the sphere can be computed. The great circle arcs joining these points on the sphere simply correspond to the dual edges present in the quad edge structure. An example of such a spherical subdivision obtained from a polyhedron is shown in fig. 1.

The result is the embedding of an undirected graph on the sphere. This embedding is actually a subdivision since a simple argument (which we omit) shows that no two of the great circle arcs we introduce can intersect, except at an endpoint. The edges of this subdivision are in a one-to-one correspondence with the edges of the polyhedron, the faces of the subdivision with the vertices of the polyhedron (including, if unbounded, the point at infinity), and vice versa. The value of constructing this subdivision is that maximizing an objective function is equivalent to locating a point in the subdivision. The way that an objective function is mapped onto a point on the sphere is as follows. Imagine a plane such that the objective function is constant on it. There are many such planes, all parallel to each other. Now take such a plane very far out, where the objective function is extremely large, and move it parallel to itself until it becomes tangent to the sphere. The point of tangency is the point we want. Equivalently, if the objective is to maximize $ax+by+cz$, the corresponding point is $(a^\prime, b^\prime, c^\prime)$, where $(a^\prime, b^\prime, c^\prime)$ is $(a, b, c)$ normalized so that $a^{\prime2}+b^{\prime2}+c^{\prime2} = 1$.

When we locate this point in the spherical subdivision, the following cases can arise. The point may lie inside a face of the subdivision. Then our linear programming problem attains its unique maximum in the corresponding vertex of the polyhedron, unless the vertex in question is the point at infinity, in which case the LP problem is unbounded. Or it may lie on an edge of the subdivision, in which case the linear programming problem is optimized along the dual edge of the polyhedron. And lastly it may coincide with a vertex of the subdivision, in which case our polyhedron has a face (dual to the vertex in question) all of whose points maximize the objective function.

It remains to describe an algorithm for the point location in a spherical subdivision problem. Corresponding algorithms for point location in a straight line subdivision of the plane have been investigated for some time. The culmination of these methods was the result of Kirkpatrick [\Kirk] who obtained a structure that uses $O(n)$ space, can be constructed in $O(n)$ time, and allows point location in $O(\lg n)$ time. It is a straighforward task to adapt Kirkpatrick's method to also work for spherical subdivisions delimited by great circle arcs. Alternatively one can map the spherical subdivision into two planar subdivisions on the tangent planes to the unit sphere at the points $(0, 0, 1)$ and $(0, 0, -1)$ by radial projection. Such a projection maps great circle arcs into straight line segments. So given the point we wish to locate, we first determine whether it is above or below the equator. If it is above, then we locate its radial projection on the upper planar subdivision, else symmetrically on the lower. Some care is required with vertices of the original spherical subdivision that lie on the equator.

This description completes the proof of our claim. We remark that an analogous, but much simpler construction, also works for two dimensions.

The corresponding spherical construction has obvious equivalents in any dimension. The difficulty is that the convex polyhedron we must compute no longer has size linear in the the number of constraints. For example in four dimensions, the number of its vertices can become quadratic in the number of constraints. Even if this is acceptable, because constructing the spherical subdivision is a cost paid once only, there are other difficulties in the point location part. No truly good algorithms for this problem are known in dimensions greater that two. It is, however, likely that polylog point location algorithms do exist for any fixed dimension.

\ref [\Baum] {Baumgart, B. G. {\it A Polyhedron Representation for Computer Vision}. AFIPS Conference Proceedings, Vol. 44, 1975 National Computer Conference, pp. 589--596.}

\ref [\Sham] {Shamos, M. I., {\it Computational Geometry}. Ph. D. dissertation, Yale University, 1977.}

\ref [\Megid] {Megiddo, N. {\it Linear-Time Algorithms for Linear Programming in $R^3$ and Related Problems}. Proceedings of the 23-rd Annual FOCS Symposium, pp. 329--338 (1982).}

\ref [\PrepMul] {Preparata, F. P., and Muller, D. E. {\it Finding the Intersection of $n$ Half-Spaces in Time $O(n \lg n)$}. Theor. Comp. Sc., 8, 45-55 (1979).}

\ref [\GuibStolf] {Guibas, L. J., and Stolfi, J. {\it Primitives for the Manipulation of Planar Subdivisions and the Computation of Voronoi Diagrams}. To appear in the Proceedings of the 15-th Annual STOC Symposium, (1983).}

\ref [\Kirk] {Kirkpatrick, D. {\it Optimal Search in Planar Subdivisions}. SIAM J. Comp., vol. 12, no. 1, pp. 28--35, (1983).}

\vskip 24pt plus 2pt minus 2pt
\hrule
\vskip 4pt