α-Concave hull, a generalization of convex hull
| Autor: | Saeed Asaeedi, Ali Mohades, Farzad Didehvar |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Convex hull
General Computer Science Convex set 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Geometry 01 natural sciences Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Hull 0202 electrical engineering electronic engineering information engineering Tight span Mathematics::Metric Geometry 020201 artificial intelligence & image processing Output-sensitive algorithm Gift wrapping algorithm Orthogonal convex hull Mathematics Alpha shape |
| Zdroj: | Theoretical Computer Science. 702:48-59 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2017.08.014 |
| Popis: | 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< |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect