The minimum perimeter convex hull of a subset of a point set?

This can be done in O(kn^3) time and O(kn^2) space (or maybe O(kn^3) if you want the actual points).

Up vote 14 down vote favorite 2 share g+ share fb share tw.

Given n points on the plane. No 3 are collinear. Given the number k.

Find the subset of k points, such that the convex hull of the k points has minimum perimeter out of any convex hull of a subset of k points. I can think of a naive method runs in O(n^k k log k). (Find the convex hull of every subset of size k and output the minimum) I think this is a NP problem, but I can't find anything suitable for reduction to.

Anyone have ideas on this problem? An example, the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3 Result: {(0,0),(0,1),(1,0)} Since this set contain 3 points the convex hull of this set is minimum out of any other sets of 3 points. Algorithm computational-geometry link|improve this question edited Jun 21 '10 at 20:35 asked Jun 21 '10 at 18:30Chao Xu53429 80% accept rate.

You might want to post code or pseudocode for those who have no idea where to start with convex hulls and computational geometry, but might have ideas for improving your algorithm. – Ben Gartner Jun 21 '10 at 18:34 @Nikita thx, I just edit it. – Chao Xu Jun 21 '10 at 18:40 Would using an MST made with the distances between points as weights potentially simplify the problem somehow?

I can think of how it would make things a bit easier in some cases, at least (but I can also think of cases where it might not be very useful). – JAB Jun 21 '10 at 18:41 2 I wonder if maybe a Voronoi Diagram might be helpful in solving this. Since this would give you all the nearest neighbors to a point I would expect that you have at least to iterate through quite a few points less for every point that you test.

(Oh, of course the MST implies that you know the nearest neighbors already) – Quasimondo Jun 21 '10 at 20:06 Can you give an example of a set of points where there is more than one possible convex hull? The more I've thought about it, the more it seems like that is an impossible situation. – MikeD Jun 21 '10 at 20:27.

This can be done in O(kn^3) time and O(kn^2) space (or maybe O(kn^3) if you want the actual points). This paper: win.tue.nl/~gwoegi/papers/area-k-gons.pdf by Eppstein et al, has algorithms to solve this problem for minimum perimeter and other weight functions like area, sum of internal angles etc which follow certain constraints, even though the title says minimum area (See Corollary 5.3 for perimeter). The basic idea is a dynamic programming approach as follows (read the first few paragraphs of Section 4): Suppose S is the given set of points and Q is the convex hull of k points with minimum perimeter.

Let p1 be the bottom-most point of Q, p2 and p3 are the next points on the hull in counter-clockwise order. We can decompose Q into a triangle p1p2p3 and a convex hull of k-1 points Q' (which shares the side p1p3 with triangle p1p2p3). The main observation is that Q' is the optimal for k-1, in which the bottommost point is p1 and the next point is p3 and all the points of Q' lie on the same side of the line p2->p3.

Thus maintaining a 4d array of optimum polygons for the each quadruple (pi, pj, pk, m) such that the polygon is a convex hull of exactly m points of S. Pi is the bottom most point of the polygon. Pj is the next vertex in counter-clockwise order, all points of the polygon lie to the left of the line pi -> pj.

All points lie on the same side of pj->pk as pi does. Can help us find the optimum polygons for m=k, given the optimum polygons for m Hope that helps.

2 The paper references finding minimum perimeter k-gons in O(n log n + k4n) which might be of interest if k is much smaller than n. – Matthieu M. Jun 22 '10 at 7:02 @Matthieu: Good observation!

– Aryabhatta Jun 22 '10 at 7:17 It's you again :D how do you manage to find all these papers? – Chao Xu Jun 22 '10 at 12:09 It you again too :D! How do you manage to find such nice questions?

;-) – Aryabhatta Jun 22 '10 at 13:00 @Mgccl. Sorry I didn't really answer your question. I am not really sure how I came upon this.

This was late last night and I forget! (Sorry for not answering your question again) – Aryabhatta Jun 22 '10 at 17:31.

It's not exactly pretty solution. In fact, it's quite a pain to implement, but it surely gives polynomial complexity. Although complexity is also big (n^5*k is my rough estimate), someone may find a way to improve it or find here an idea for better solution.

Or it may be enough for you: even this complexity is much better than bruteforce. Note: optimal solution (set S) with hull H includes all points from orignal set inside H. Otherwise, we could throw away one of the border points of H and include that missed point, reducing perimeter.

(update just like 'optimization' mbeckish posted) Assumption: no two points from the set form a vertical line. It can be achieved easily by rotating whole set of points by some irrational angle around origin of coordinates. Due to assumption above, any complex hull has one leftmost and one rightmost point.

Also, these two points divide the hull into top and bottom parts. Now, let's take one segment from the top part of this hull and one from the bottom part. Let's call those two segments middle segments and perimeter of the right part of this hull - right perimeter.

Note: those two segments is all we need to know about right part of our convex hull to continue building it to the left. But having just two points instead of 4 is not enough: we could not uphold condition of 'convexness' this way. It leads to a solution.

For each set of points {p0, p1, p2, p3} and number I (i 1: you'll have to include all points in the triangle {p, p0, p2}. They aren't on the hull, but inside it. Algorithm is over :) In addition, despite scary complexity, you may note that not all segments p0, p1, p2, p3 can be middle segments: it should reduce actual computation time substantially.

Update This provides only optimal perimeter size, not the set itself. But finding the set is simple: for each 'state' above you store not only perimeter size, but also last point added. Then, you can 'trace' your solution back.

It's quite standard trick, I suppose it's not a problem for you, you seem to be good at algorithms :) update2 This is essentially DP (dynamic programming), only a bit bloated.

Like the overall approach - A DP approach seems like the way to go. Also the brute force approach should have complexity C(n,k) (not n^k) *k*log(k) which for some problems with k – andand Jun 22 '10 at 2:47 @andand k=3 is the worst way to 'simplify' this algorithm: it would essentially come down to trying all combinations of three points. I'd suggest to get familiar with DP first: it's a really generic technique which can help you with lots of different problems.

– Nikita Rybak Jun 22 '10 at 3:19 1 @Nikita Rybak Refrering to "rotating whole set of points by some irrational angle" ... for example 2*PI :) – belisarius Jun 22 '10 at 4:31 @Beta: I wasn't looking to simplify the problem. What I was saying is that I don't see how your algorithm will ever consider triangular convex hulls as a potential solution. If the actual solution turns out to be a triangle, how will your algorithm detect it?

– andand Jun 22 '10 at 13:09.

One possible optimization: You can ignore any subsets whose convex hull contains points that are not in the subset. Proof: If your convex hull contains points that are not in your subset, then remove a point from your subset that is on the hull, and replace it with a point in the interior of the hull. This will yield a hull of equal or smaller perimeter.

In order to ignore those subsets you have to compute their convex hulls (or at least find if their convex hulls contain points that aren't in the subset), so you're not actually ignoring them. – IVlad Jun 21 '10 at 19:42 Also, if you replace a hull point with one that is in the hull's interior, the new hull isn't necessarily convex. So when you regenerate the convex hull it may not include the interior point and you will have a convex hull with less than K points.

Consider a pentagonal convex hull with an additional interior point at its center. Replace any vertex with that center point and the resulting polygon will not be convex. – A.

Levy Jun 21 '10 at 20:14 @A. Levy - When you regenerate the convex hull, the newly selected point will need to be either on or inside the convex hull, or else you regenerated the convex hull incorrectly. – mbeckish Jun 21 '10 at 20:50 @IVlad - The idea is that once you find one convex hull with extra interior points, you use that knowledge to prune some other permutations of points in advance.

For example, consider k = 30, and say that a certain subset yields a convex hull with 3 points on the hull, and extra interior points. You can now eliminate all permutations of the 3 points on the hull and the possibly thousands of points outside of the hull, because any such subsets would yield a hull that contains the original hull, and thus should be ignored. – mbeckish Jun 21 '10 at 21:07 By "You can now eliminate all permutations of the 3 points on the hull and the possibly thousands of points outside of the hull", I mean any subsets that include the 3 points on the original convex hull, plus k-3 other points from the set of points exterior to the convex hull.

– mbeckish Jun 21 '10 at 21:09.

In the planar case, you can use an algorithm known as the Jarvis march, which has worst case complexity O(n^2). In this algorithm, you start building a hull at an arbitrary point and then check which point needs to be added next. Pseudocode taken from wikipedia: jarvis(S) pointOnHull = leftmost point in S I = 0 repeat Pi = pointOnHull endpoint = S0 // initial endpoint for a candidate edge on the hull for j from 1 to |S|-1 if (Sj is on left of line from Pi to endpoint) endpoint = Sj // found greater left turn, update endpoint I = i+1 pointOnHull = endpoint until endpoint == P0 // wrapped around to first hull point As far as I understand it, convex hulls are unique to each set of points, so there is no need to find a minimum.

You just find one, and it will be the smallest one by definition. Edit The posted solution solves for the convex hull with the fewest number of points. Any hull with more points will have a longer perimeter, and I misunderstood the question to seeking a minimum perimeter, instead of a minimum perimeter for a set with K points.

This new problem is probably NP as suspected, and most similar to the longest path problem. Unfortunately, I lack the ingenuity to provide a worthwhile reduction.

3 This gives you a convex hull algorithm - he's trying (I think) to find the best subset K from the points in N where the hull of K is a minimum. This just generates a hull - but doesn't answer the "real" question, from my reading of it. – Reed Copsey Jun 21 '10 at 18:42 But that's the thing: He wants to know an algorithm to find WHAT set of points provides the smallest convex hull for the specified number of points.

– JAB Jun 21 '10 at 18:42 3 Did you by any chance stop reading the question after seeing the words "convex hull"? – IVlad Jun 21 '10 at 18:42.

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.