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

DOI10.1016/S0304-3975(01)00054-8zbMath0997.68153MaRDI QIDQ1603641

Malika More, Rémy Malgouyres

Publication date: 15 July 2002

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

zbMATH Keywords

computational complexityreachabilityhomotopydigital topology

Mathematics Subject Classification ID

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

Related Items (3)

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

Cites Work

• Bounded-depth, polynomial-size circuits for symmetric functions
• A topological characterization of thinning
• Homotopy in two-dimensional digital images
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Definability by constant-depth polynomial-size circuits
• Problems complete for deterministic logarithmic space
• Adjacency in digital pictures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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