α-Concave hull, a generalization of convex hull
Copyright policy )α-Concave hull, a generalization of convex hull
Bounding hull, such as convex hull, concave hull, alpha shapes etc. has vast applications in different areas especially in computational geometry. Alpha shape and concave hull are generalizations of convex hull. Unlike the convex hull, they construct non-convex enclosure on a set of points. In this paper, we introduce another generalization of convex hull, named alpha-concave hull, and compare this concept with convex hull and alpha shape. We show that the alpha-concave hull is also a generalization of an NP-complete problem named min-area TSP. We prove that computing the alpha-concave hull is NP-hard on a set of points.
- Amirkabir University of Technology Iran (Islamic Republic of)
Computational Geometry (cs.CG), FOS: Computer and information sciences, \(\alpha\)-concave hull, Approximation algorithms, minimum area polygon, Computer graphics; computational geometry (digital and algorithmic aspects), Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, \(\alpha\)-shape, convex hull, approximation algorithm, NP-complete
Computational Geometry (cs.CG), FOS: Computer and information sciences, \(\alpha\)-concave hull, Approximation algorithms, minimum area polygon, Computer graphics; computational geometry (digital and algorithmic aspects), Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, \(\alpha\)-shape, convex hull, approximation algorithm, NP-complete
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).56 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!