2

Given a set of points in the plane, I want to find the smallest polygon containing all the points. More precisely, the vertices of this polygon must be a subset of the original set of points.

The easiest approach would be to find the convex hull, which can be computed in O(N log(N)) time using Graham's scanning algorithm, but I would ideally like to drop the requirement that the polygon be convex. Are there any standard approaches to this? I imagine this problem is a fair bit harder because it seems to me there is not guaranteed to be a unique solution.

Zach Conn
  • 1,301
  • 2
  • 11
  • 23
  • 2
    It should be possible to find a concave polygon with zero area that contains all points. Maybe you want to add some more details? – Niklas B. Mar 25 '14 at 15:37
  • I'm not immediately sure exactly what you have in mind, but the polygon should avoid things like self-intersections, etc. Certainly a solution of zero area is not desired unless the points are collinear (which we can assume for simplicity will never be the case). – Zach Conn Mar 25 '14 at 15:51
  • Depending on how you define a polygon, the area in question is either zero or is very hard to find. I'm almost sure there are no known methods other than sheer brute force. Why do you need this? – n. m. could be an AI Mar 25 '14 at 15:51
  • Maybe you will be interested in [this question](http://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull) and its answers – Niklas B. Mar 25 '14 at 15:54
  • @Niklas B.: I see now what you mean. I would exclude a spanning tree from counting as a polygon in my case, even though I can see that it technically counts as a solution. The link you have provided does indeed seem to agree with what I'm qualitatively looking for. I want to characterize the 'shape' of a set of points in the plane in a way that is more accurate than the convex hull. Apologies for my trouble in finding a formal problem statement for this. – Zach Conn Mar 25 '14 at 15:58
  • @ZachConn I think the problem is that even if you exclude the special case I mentioned, you have a lot of cases where you can build some kind of polygon of very small area which does not at all characterize the shape of your point set. So usually you want some kind of concavity parameter. I think the problem is usually called [concave hull](http://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for-concave-hull) – Niklas B. Mar 25 '14 at 16:00
  • 2
    Look at the `alpha shapes` – MBo Mar 25 '14 at 18:00
  • Do you allow polygons with holes ? –  Mar 26 '14 at 09:31
  • @YvesDaoust: Ideally yes, if the points were distributed roughly in the shape of, say, a torus, then the result of the algorithm should be a polygon shaped like a torus (with a 'hole' in the middle). This is actually a good example for showing why the convex hull is really insufficient for characterizing the "shape" of a set of points. – Zach Conn Mar 26 '14 at 15:08
  • Then if you don't add constrains, solutions could be "sponge"-like with numerous holes. I don't think this is what you want. I think you have alpha-shapes in mind, don't you ? –  Mar 26 '14 at 15:14
  • Yeah, alpha shapes definitely seem to be what I'm looking for based on a cursory glance. I wasn't familiar with the term and was grasping for a way to formalize the problem--it's clear to me now that the phrasing in terms of minimal area is not what I really wanted. – Zach Conn Mar 26 '14 at 15:31

1 Answers1

5

Do you need the absolutely smallest area solution or just a 'fairly good' solution. If the latter then one possible algorithm would be: 1) calculate the convex hull of all your points - all these points must be vertexes of your final solution. 2) calculate the convex hull of the remaining points - repeat this process until you have no points left. You will end up with n non-intersecting convex hulls. 3) Determine (possibly by greedy algorithm), where to join these hulls to form a single contiguous path between all the points by adding pairs of lines between neighboring points in neighboring hulls and removing lines in the hulls.

This might not be the minimal area but should be a fairly good solution.

Added comment: Greedy removal from the outermost hull to the next inner one should be by removing the largest area region separating the two. Greedy removal from the second hull to the next inner one should be by 'removing' (which is actually retaining) the smallest area separating the hulls...and so on inwards swapping between largest and smallest areas...

Picture added to explain better than my 100 words. Algorithm in a picture

Penguino
  • 2,136
  • 1
  • 14
  • 21
  • This thing that you made... should be called something, do you know how is it called? – Goodwine Mar 27 '14 at 20:43
  • 2
    I just though t it up - call it Wilbur if you like. – Penguino Mar 30 '14 at 21:30
  • Even though I think alpha shapes are more appropriate for what I actually wanted, your answer is more in line with what I actually asked--so I'm giving you the best answer. – Zach Conn Apr 16 '14 at 22:00