Minimum decomposition of a digital surface into digital plane segments is NP-hard

DOI10.1016/j.dam.2008.05.028zbMath1168.68049OpenAlexW2052752306MaRDI QIDQ1003721

Isabelle Sivignon, David Coeurjolly

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.05.028

zbMATH Keywords

complexitydecompositiondigital planedigital object

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Maximal Planes and Multiscale Tangential Cover of 3D Digital Objects ⋮ Some theoretical challenges in digital geometry: a perspective ⋮ An alternative definition for digital convexity ⋮ Close-to-optimal algorithm for rectangular decomposition of 3D shapes

Cites Work

• Digital planarity -- a review
• Digital straightness -- a review
• Decomposition of a three-dimensional discrete object surface into discrete plane pieces
• Strategies for polyhedral surface decomposition: an experimental study.
• On the min DSS problem of closed discrete curves
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum decomposition of a digital surface into digital plane segments is NP-hard