6
$\begingroup$

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

  • 0
    What do you mean by *convex position*?2012-07-19
  • 2
    @P23 A point set is in convex position if every point of the set is a vertex of its convex hull.2012-07-23
  • 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
    I would recommend the [approach taken at CS.SE](http://cs.stackexchange.com/questions/1940/if-a-point-is-a-vertex-of-convex-hull/2070#2070) 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).](http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cgcourse/cs372l09.pdf)2012-08-01
  • 0
    @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?2012-08-01
  • 0
    @WillJagy If three of the points are collinear, the one in the middle won't be a vertex of the hull.2012-08-02
  • 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.