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

  • $\begingroup$ What do you mean by convex position? $\endgroup$ – Jacob Jul 19 '12 at 22:23
  • 2
    $\begingroup$ @P23 A point set is in convex position if every point of the set is a vertex of its convex hull. $\endgroup$ – stefan Jul 23 '12 at 8:56
  • $\begingroup$ I believe this could point you in the right direction. $\endgroup$ – 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.

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.

  • $\begingroup$ 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). $\endgroup$ – Zairja Aug 1 '12 at 20:55
  • $\begingroup$ @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? $\endgroup$ – Will Jagy Aug 1 '12 at 23:11
  • $\begingroup$ @WillJagy If three of the points are collinear, the one in the middle won't be a vertex of the hull. $\endgroup$ – Andy Barfoot Aug 2 '12 at 12:38
  • $\begingroup$ @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. $\endgroup$ – stefan Aug 2 '12 at 19:13

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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