α-Concave hull, a generalization of convex hull

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