Solving geometric problems using Linear Programming

Question

Is it possible to find an LP formulation to test whether $n$ points in the plane are in convex position?

Answer 1

I don't know about an LP approach, but there are many good choices, see WOOKIE. If you have $n$ points and a convex hull algorithm produces a polygon with fewer than $n$ vertices, then the $n$ were not in convex position.

As pointed out in comment below, there is a difference between convexity and strict convexity. What I had in mind, producing the convex hull as a sequence of vertices wrapping around the polygon in counterclockwise order, allows one to choose which concept is desired during execution of the algorithm.

Answer 2

If you are really interested in using linear programming then this might be one method to try. Suppose that $v_1,\ldots,v_k$ are the vertices that you are interested in testing. Define the polytope $P=\{(x,\lambda) \mid x = \sum_{i=1}^k \lambda_i v_i,\; \sum_{i=1}^k \lambda_i = 1,\; \lambda_i \geq 0 \quad \forall i=1,\ldots,k\}$. Observe that the variables are $x$ (a vector) and $\lambda_1,\ldots,\lambda_k$. Notice that all feasible $x$ describes the convex hull of $v_1,\ldots,v_k$. Now you can use the simplex method and reverse search to enumerate all the vertices of this polytope. Avis and Fukuda have a few papers on reverse search for polytope vertex enumeration.

Let me note that this is probably not the fastest way to perform this test especially in the plane.