Home Bookmarks Papers Blog

Two dimensional linear programming

Applet By Evgeny Gonopolsky

Linear programming is the problem of deciding whether there exists a solution to a system of linear ineqalities. Alot of work was gone into this problem, resulting in the classical SIMPLEX algorithm (which is exponential in the worst case), and the Ellipsoid method. The SIMPlEX algorithm is exponential in the worstcase, and the Ellipsoid algorithm is weakly polynomial. Coming up with a strongly-polynomial time algorithm for the linear programming problem is one of the major open problems in computer science.

However, if the number of variables in the system of inequalities is small (2, 3, or even a small constant) better methods are known. In this applet we demonstrate Megiddo algorithm (independently discovered by Dyer) for the planar case. Here, each inequlity:

ai x + bi y <= ci

corresponds to half of the plane (because, ai x + bi y = ci is a line, and all the points that lie to one side of this line fulfill this inequality). We know that there is a solution if the intersection of the all those regions is not empty (i.e. the feasible region). In fact, usually we also wish to find a solution that minimizes (or maximizes) a linear function (i.e. objective function).
First, we apply a linear transformation to the points of  the plane, so that the objective function becomes equal to the negative y-axis. This reduces the problem to  finding the lowest point in the region defined by the constraints.

Description of the algorithm

The intuition behind the algorithm is the following: there are only half-planes that define the solution (i.e. their intersection point). If we can throw away, repeatedly, a large chunk of the inequlities because we know that they do not participate in the soltion, than by the end of this shrinking process we will be left by a small number of constraints (that we know that they define the optimal solution). Now, we will compute the solution from this subset of the inequalities.

Pseudocode the algorithm

  1. Rotate the coordinate system, so that the objective function becomes the negative y-axis
  2. Partition the half planes (i.e. constraints) into three groups, depending upon whether the "allowed" half-plane defined by the constraint lies:
    1. Above the line defining the constraint (the contraint is a "floor" of the feasible region)
    2. Below the line defining the constraint (a "ceiling" of the feasible region)
    3. Left or right of the line - the line is vertical.
  3. If there are at most one "floor" constraint left, then decide, where is the optimum - the lowest point (if it exists) in constant time and go to stage 7
  4. Partition the "floors" and "ceilings" into the pairs (in an arbitrary manner). If the lines in a pair are parallel or their intersection point is not between the  left and right bounds, determined by the vertical constraints, then remove one of them (because one of them does not participate in definining the solution).
  5. Find the median of those intersection points (median in the x coordinate of the points), and decide where is the optimum point relative to the median. If it has the same x coordinate, then go to stage 7
  6. For each pair, with intersection point on opposite side of the optimum (relative to the median), remove one of the half planes (one of them does not participate in the defining the solution) and go to the stage 3
  7. Rotate the coordinates back and report the solution

Running Time

If at the beginning of stage 4 there are M constraints in the "floors" and  "ceilings",  then at the stage 6 at least M/4 constraints  are removed (for example we thrown one half-plane from all the intersection points to the right of the median). There are M/2 intersections, we thus removed a constraint from M/4 pairs. Thus, we removed M/8 constraints. Overall, this required O(M) time. Repeating this process will require:
O(M + 7/8M + (7/8)2M + ... ) = O(M)
time. This follows because finding the median can be done in linear time. Thus, the overall running time of the algorithm is O(M).

The Applet

    The algorithm is describedi n detain in:
Franco P. Preparata, Michael Ian Shamos , "Computational geometry" (Second printing), Springer-Verlag, 1985.
Back to the Workshop home page