-concave hull, a generalization of convex hull

DOI10.1016/J.TCS.2017.08.014MaRDI QIDQ1676320zbMATH OpenOpenAlexFDO

Authors Saeed Asaeedi, F. Didehvar, Ali Mohades

Publication date 6 November 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7829

zbMATH Keywords

approximation algorithmconvex hullNP-complete\(\alpha\)-shape\(\alpha\)-concave hullminimum area polygon

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: 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.

Recommendations

• Convex hulls of \(f\)- and \(\beta\)-vectors
• scientific article; zbMATH DE number 1405409
• On a generalization of alpha convexity
• On the shape of \(p\)-convex hulls, \(0<p<1\)
• Convex hulls of algebraic sets
• Convex hull of planarh-polyhedra
• On convex hulls
• A characterization theorem and an algorithm for a convex hull problem
• Convex hulls of objects bounded by algebraic curves

Cites work

• scientific article; zbMATH DE number 1189236 (Why is no real title available?)
• scientific article; zbMATH DE number 3617544 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445366 (Why is no real title available?)
• scientific article; zbMATH DE number 7618482 (Why is no real title available?)
• A Lower Bound for Heilbronn'S Problem
• A New Convex Hull Algorithm for Planar Sets
• A global optimization RLT-based approach for solving the hard clustering problem
• A lower bound for Heilbronn's triangle problem in \(d\) dimensions
• An Algorithm for Convex Polytopes
• An Upper Bound for the d-Dimensional Analogue of Heilbronn's Triangle Problem
• An efficient algorithm for determining the convex hull of a finite planar set
• Applications of graph and hypergraph theory in geometry
• Approximate Delaunay mesh reconstruction and quality estimation from point samples
• Computational Geometry in C
• Convex hulls of finite sets of points in two and three dimensions
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Image registration and object recognition using affine invariants and convex hulls
• Large triangles in the \(d\)-dimensional unit cube
• On Heilbronn's Triangle Problem
• On Heilbronn's problem in higher dimension
• On a Problem of Heilbronn
• On a Problem of Heilbronn, II
• On a Problem of Heilbronn, III
• On a Problem of Heilbronn†
• On simple polygonalizations with optimal area
• On the identification of the convex hull of a finite set of points in the plane
• On the shape of a set of points in the plane
• Protein structure optimization by side-chain positioning via beta-complex
• Reconstruction of polygonal shapes from sparse Fourier samples
• The complexity of incremental convex hull algorithms in \(R^ d\)
• The on-line Heilbronn's triangle problem in \(d\) dimensions

Cited in

(3)

• Selection of \(\alpha \) for \(\alpha \)-hull and formulation of fuzzy \(\alpha \)-hull in \(\mathbb{R}^{2}\)
• Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms
• Convex hulls of \(f\)- and \(\beta\)-vectors

Describes a project that uses

Uses Software

• BetaSCP

This page was built for publication: \(\alpha\)-concave hull, a generalization of convex hull

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1676320)