Authors | Saeed Asaeedi - Farzad Didehvar - Ali Mohades |
---|---|
Journal | Theoretical Computer Science |
Page number | 12 |
IF | 1.002 |
Paper Type | Full Paper |
Published At | 2017-11-30 |
Journal Grade | ISI |
Journal Type | Typographic |
Journal Country | Netherlands |
Abstract
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
tags: Convex hull, α-Shape, α-Concave hull, Minimum area polygon, NP-complete, Approximation algorithm