# Is there an algorithm to find an almost-convex hull given a tolerance angle?

I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows more closely the "perimeter". And if there is a definition of a non intersecting perimeter of a set of points, in this case the resulting polygon when $\alpha$ is big.

Another view of the problem can be to find an algorithm that can be parametrized to find for $\alpha = 0$ the minimum perimeter solution (convex-hull) and for $\alpha = 1$ (normalized) the minimum area polyline enclosing all the points.

• Have you looked into the concept of strongly convex sets? Jul 24, 2012 at 16:19
• Could you clarify the purpose of $\alpha$? What purpose does it serve?
– Paul
Jul 24, 2012 at 17:42
• Would it be allowed to propose an algorithm that does more work as $\alpha$ grows? Or did you expect increasing $\alpha$ would decrease "expected" complexity?
– hardmath
Jul 25, 2012 at 4:46
• I intended it as the angle the algorithm is allowed to move away from the convex hull. And no, I don't think it will decrease the complexity. Jul 25, 2012 at 10:44
• These concave_hulls ideas could be usefull to you. Nov 10, 2021 at 16:20

You might investigate the so-called alpha-hull, for example: CRAN package, Wikipedia on alpha shapes: This may be too simple to be of interest, but one approach would be to find the convex hull and use the polygonal boundary segment by segment to locate additional points that satisfy the $\alpha$-angle criterion, stopping once a full circuit has been completed without adding further vertices. More than once pass may be required to reach "convergence".
The $\alpha$-angle criterion may be formulated for a given pair of consecutive boundary vertices as lying in a region between a circular arc and its chord = boundary segment. One might term this a circular segment.