# “Concave hull” - Possible? Feasible? Deterministic?

So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm would define a pentagon around a five-point star and call that the convex hull, but if I wanted to identify the shape as a five-pointed star that would be insufficient.

How then could I tell the computer to define a polygon that may be concave, which would contain all the points in Q and has nonzero area, but would minimize areas bounded by the shape in which there are no points from Q?

I'm thinking a simple tweak of the Graham Scan to allow right turns, but that would instead not allow lines to cross, might do it, but that's just a wild shot in the dark which I haven't tried. I'm also thinking that, given the normal application of this in computers (image pattern recognition), that I would also have a set of points R that should NOT be contained in the polygon, and after finding the "convex hull" of the points Q I can then run a variation of the algorithm that adds "right turns" at points that should lie outside the shape but currently are contained within.

So first define the subset H that define the convex hull of a set of points Q. Now, take each point X from a set R of points that must not be contained in the final polygon. Determine if that point lies within the polygon (it does if a line from any point in Q to X intersects zero or an even number of line segments defining the current polygon). If so, insert X into H between the two adjacent points M and N in H that have the lowest mean distance from X. Then, for all P in Q that are not in H, if P now lies outside the shape defined by H, add P to H between either M and X, or X and N, depending on which two points have the lowest mean distance. Repeat for all X in R.

Are there any proven algorithms that would accomplish this (and be less complex than O(N^2logN) given that Q and R are roughly equal in cardinality)?

-
The concave hull of a polygonal domain would be the polygonal domain itself after your definition of concave hull, so there is no new mathematical object. –  Beni Bogosel Apr 10 '12 at 22:38
OK, yes, a line connecting all dots in order without crossing over itself would be a "convex hull"; however, it would have zero area. So, the shape I'm looking for must have nonzero area. We can also state that no point may occur twice in the list of vertices produced by traversing the perimeter of the shape in one direction. –  KeithS Apr 10 '12 at 22:46
If you have a finite set of points $Q$ then there are polygons with vertices in $Q$ with area arbitrarily small. –  Beni Bogosel Apr 10 '12 at 22:51
Is minimum area really what you want? Perhaps a curve reconstruction algorithm would be better? –  Rahul Narain Apr 10 '12 at 23:34