-concave hull, a generalization of convex hull

DOI10.1016/J.TCS.2017.08.014zbMATH Open1380.68376arXiv1309.7829OpenAlexW2745787592MaRDI QIDQ1676320FDOQ1676320

Authors: Saeed Asaeedi, F. Didehvar, Ali Mohades 

Publication date: 6 November 2017

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

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)