α-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 NPhard 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 α − MAC P as an NP-hard problem similar to the problem of computing α-concave hull and present an approximation algorithm for α − MAC P. The paper ends by implementing the proposed algorithm and comparing the experimental results against those of convex hull and α-shape models