α-Concave hull, a generalization of convex hull

Bounding hulls such as convex hull, α-shape, χ-hull, concave hull, crust, etc. offer a wide variety of useful applications. In this paper, we explore another bounding hull, namely α-concave hull, as a generalization of convex hull. The parameter α determines the smoothness level of the constructed hull on a set of points. We show that it is NP-hard to compute α-concave hull on a set of points for any 0<α<π. This leads us to a generalization of Fekete work (when α=π). We also introduce α−MACP as an NP-hard problem similar to the problem of computing α-concave hull and present an approximation algorithm for α−MACP. The paper ends by implementing the proposed algorithm and comparing the experimental results against those of convex hull and α-shape models.