Largest prefix of array of vertices that forms a convex polygon?

There is a very simple O(m log m) solution to this.

Up vote 4 down vote favorite share g+ share fb share tw.

Related to: Polygon Decomposition - Removing Concave Points to Form Convex Polygons I am looking for an algorithm to do the following: The input is an array of 2D points (P0…PN-1). The length N of the array varies (3? N ) For any M?

N there may or may not be a convex polygon whose vertices are P0…PM-1 in some order. Note the edges are not necessarily adjacent pairs in the array. What is the most efficient algorithm to find the maximum M such that this convex polygon exists?

My current algorithm is very inefficient. I test with M=3 then M=4, M=5 etc., compute the hull then test that all P0…PM-1 are vertices of the hull, if not then I break out of the loop and return M-1. Example #1: (-2,2), (2,2), (-2,-2), (-1,1) result: 3 (because the first three points form a triangle but adding P3 = (-1,1) would make the polygon non-convex) Example #2: (-2,2), (2,2), (-2,-2), (1,-1) result: 4 (because a convex quadrilateral can be constructed from all 4 points in the array) Update Example #3: (-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1) result: 4.

This example demonstrates why it is not sufficient to take the convex hull of all supplied points and find a prefix that is a subset of it. (3,-3) cannot be part of a convex polygon consisting of the first five points because then the previous point (2,-1) would no longer lie on the hull. But it is (3,-3) that must be rejected, even though it lies on the hull of all six points and (2,-1) does not.

Examples of invalid inputs: (-1,-1), (0,0) (too few points) (-1,-1), (0,0), (1,1), (1, -1) (first three points are colinear: I would not expect the algorithm to be able to handle this. ) algorithm geometry convex-hull convex-polygon link|improve this question edited Jan 14 '11 at 19:53 asked Jan 14 '11 at 19:17finnw14.5k13270 95% accept rate.

– biziclop Jan 14 '11 at 19:22 @biziclop, yes I want the hull with the largest number of vertices. And I hope it can be done more efficiently than computing the hull for each possible size. – finnw Jan 14 '11 at 19:27 As biziclop mentioned: this is just a matter of finding the convex hull of a set of points.

The number of points laying on the edge of this convex hull is your size. So, O(n*log(n)) using Graham's Scan, or the Quick-Hull algorithm. Or am I missing something?

– Bart Kiers Jan 14 '11 at 19:28 1 @Bart Kiers, not quite. I am only interested in hulls that are prefixes of the array. I must stop scanning the array when I see a point that cannot be part of the hull.

Any subsequent points must be ignored even if they could be part of a (different) hull. – finnw Jan 14 '11 at 19:31 @Bart Kiers, I have added example #3 to illustrate this. – finnw Jan 14 '11 at 19:53.

There is a very simple O(m log m) solution to this. Given that there are at least 3 points and the first 3 are not collinear: Find a point, P, in the triangle of the first 3 points. Sort the 3 points by their angle relative to P (counterclockwise).

(This sorted list will be the convex hull) While we aren't at the end of the list, find the next point's position in the sorted list. If inserting the point will make the polygon concave, goto 6. (This can be checked by just checking the new neighboring two turns and the current turn) Insert the point and goto 3.

Done. The main edge case that you have to handle here is when the insertion is at one of the ends of the list, since the list is actually circular. One simple way to handle this is for each point insert it at its angle and at its angle +- 2pi.

I think you want an incremental convex hull. Here are a few links: personal.kent.edu/~rmuhamma/Compgeometry... ww3.algorithmdesign.net/handouts/Increme... fandm.edu/computer-science/professors-em....

You can do this in O(m lg m) time. Store the upper hull and lower hull points in search trees keyed by X coordinate. When a new point arrives, find the upper and lower line segments covering its X value (search the trees).

If the new point is between the two lines, then it is not on the hull. Give up. Otherwise, insert the point into the upper or lower hull (whichever has the closer line segment).

If inserting the point turned the adjacent points into interior corners, then they are not on the hull. Give up. Deal with edge cases like new left-most point, vertical points, etc. Continue until the desired number of points are processed.

I was in the middle of posting roughly the same reply when your answer popped up. – oosterwal Jan 14 '11 at 21:00.

Every time the entire prefix forms a convex polygon, double the size of the prefix. Every time it fails, shrink the size of the prefix to halfway between the current size and the previous size.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.