# Solving geometric problems using Linear Programming

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

• What do you mean by convex position? – Jacob Jul 19 '12 at 22:23
• @P23 A point set is in convex position if every point of the set is a vertex of its convex hull. – stefan Jul 23 '12 at 8:56
• I believe this could point you in the right direction. – Zairja Aug 1 '12 at 19:15

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.
• I would recommend the approach taken at CS.SE since that is $O(n)$ time versus $O(n \log n)$. I also think it lends itself to LP similar to constructing the "feasible region" (of convex shape). – Zairja Aug 1 '12 at 20:55
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.