Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What do you mean by convex position? –  Jacob Jul 19 '12 at 22:23
2  
@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
add comment

2 Answers

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.

share|improve this answer
    
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
    
@Zairja, maybe you could work up an answer. As is often the case, we do not know whether the important thing here for is a quality algorithm or a method that fits into an LP style. I would guess that "stefan," who posted the bounty, wants an LP answer. Note that there are two answers deleted by the answerers, one on July 23 which seemed inconclusive, one just a few hours ago. As always, how much effort to put in is a matter of taste. Location Computadora? –  Will Jagy Aug 1 '12 at 23:11
    
@WillJagy If three of the points are collinear, the one in the middle won't be a vertex of the hull. –  Andy Barfoot Aug 2 '12 at 12:38
    
It's probably enough if we establish that this question is equivalent to constructing the convex hull. Then we have an LP-problem that is equivalent to constructing the convex hull which constructs the delaunay triagulation or the voronoi diagramm - all of which is a new result afaik. –  Peter Sheldrick Aug 2 '12 at 16:59
    
@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. –  stefan Aug 2 '12 at 19:13
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.