Finding a minimum medial axis of a discrete shape is NP-hard

DOI10.1016/j.tcs.2008.06.013zbMath1160.68040OpenAlexW2028302408MaRDI QIDQ952462

Isabelle Sivignon, David Coeurjolly, Jérôme Hulin

Publication date: 12 November 2008

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.013

zbMATH Keywords

NP-completenessbounded approximation algorithmminimum medial axis

Mathematics Subject Classification ID

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

Related Items (4)

Exact and optimal conversion of a hole-free 2\textsc{d} digital object into a union of balls in polynomial time ⋮ Some theoretical challenges in digital geometry: a perspective ⋮ Fast distance transformation on irregular two-dimensional grids ⋮ Appearance Radii in Medial Axis Test Mask for Small Planar Chamfer Norms

Cites Work

• Unnamed Item
• Unnamed Item
• The minimum broadcast time problem for several processor networks
• A unified linear-time algorithm for computing distance maps
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Medial axis for chamfer distances: computing look-up tables and neighbourhoods in 2D or 3D
• Sequential Operations in Digital Picture Processing

This page was built for publication: Finding a minimum medial axis of a discrete shape is NP-hard