On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology

DOI10.1016/S0304-3975(01)00054-8MaRDI QIDQ1603641zbMATH OpenFDO

Authors Rémy Malgouyres, Malika More

Publication date 15 July 2002

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

zbMATH Keywords

computational complexityhomotopyreachabilitydigital topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10)

Recommendations

• Computational Complexity of Two-Dimensional Regions
• Homotopy in two-dimensional digital images
• Topological Complexities of Finite Digital Images
• Concepts of digital topology
• A theory of binary digital pictures

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4211535 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• A topological characterization of thinning
• Adjacency in digital pictures
• Bounded-depth, polynomial-size circuits for symmetric functions
• Definability by constant-depth polynomial-size circuits
• Homotopy in two-dimensional digital images
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Problems complete for deterministic logarithmic space

Cited in

(3)

• In-place algorithm for erasing a connected component in a binary image
• Some theoretical challenges in digital geometry: a perspective
• A new algorithmic framework for basic problems on binary images

This page was built for publication: On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology

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