6
$\begingroup$

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

  • 0
    I believe [this](http://cs.stackexchange.com/a/2070) could point you in the right direction.2012-08-01

2 Answers 2

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.

  • 0
    @Will Jagy et al, thank you for your comments. I am indeed interested in an LP answer, since convexity is a constraint in a more complicated LP. I guess the constraints should be that for any point pair one of the two halfplanes through the point pair contains all other points.2012-08-02
0

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.