More Web Proxy on the site http://driver.im/

article

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

Authors:

Rémy Malgouyres,

Malika MoreAuthors Info & Claims

Theoretical Computer Science, Volume 283, Issue 1

Pages 67 - 108

https://doi.org/10.1016/S0304-3975(01)00054-8

Published: 11 June 2002 Publication History

Abstract

We study the computational complexity of some well-known problems of 2D digital topology. We prove that all considered problems (including reachability in 2D binary images, connectivity, lower homotopy and symmetric homotopy) are in LogSpace. We prove that reachability in 2D binary images and some other problems are NC1-hard. Finally, we prove that most of the considered problems are not in AC0.

References

[1]

H.M. Alnuweiri, V.K. Prasanna, Parallel architectures and algorithms for image component labelling, IEEE Trans. Pattern Anal. Mach, Intell. 14 (10) (1992) 1034-1034.

Digital Library

[2]

D.A. Mix Barrington, N. Immerman. H. Straubing, On uniformity within NC, J. Comput. System Sci. 41(3) (1990) 274-306.

Digital Library

[3]

S.R. Buss, Alogtime algorithms for tree isomorphism, comparison, and canonization, in: G. Georg, et al. (Eds.), Computational Logic and Proof Theory, 5th Kurt Godel Colloquium KGC97, Proceedings, Lecture Notes in Computer Science, vol. 289. Springer, Berlin, 1997, pp. 1833.

Digital Library

[4]

A.I. Bykov, L.G. Zerkalov, Algorithms for homotopy classification of binary images, Pattern Recognition 29(4) (1996) 565-574.

[5]

S.A. Cook, P. McKenzie, Problems complete for deterministic logarithmic space, J. Algorithms 8(1987) 385-394.

Digital Library

[6]

R. Cypher, .I.L.C. Sanz, L. Snyder, An EREW PRAM algorithm for image component labelling Correspondence in IEEE Trans. Pattern Anal. Mach, Intell. 11(3) (1989) 258-262.

Digital Library

[7]

L. Denenberg, Y, Gurevich, S. Shelah, Definability by constant-depth polynomial-size circuits, Inform and Control 70 (1986) 216-240.

Digital Library

[8]

H.P. Ebbinghaus, I, Hum, Finite Model Theory, Springer, Berlin, 1995.

[9]

R. Fagin, M. Klawe, N. Pippenger, L. Stocktneyer, Bounded-depth, polynomial-size circuits k: symmetric functions, Theoret. Comput. Set. 36 (1985) 239-250.

Digital Library

[10]

F.E. Fich, The complexity of computation on the parallel random access machine, in: .1. Reif (Ed Synthesis of Parallel Algorithms. Chapter 21, Morgan-Kaufmann, Los Altos, CA. 1993.

[11]

M. Furst, J. Saxe, M. Sipser, Parity, circuits and the polynomial hierarchy, Math. Systems Theory, 17 (1984) 13--27.

[12]

P. Hajek, P. Pudlak, Metamathematics of First-Order arithmetic, Springer, Berlin, 1993.

[13]

G. Herman, Discrete Multidimensional Jordan surfaces, Vision geometry, Proc. AMS Spec. Sess., 85 Meet., Hoboken/NJ (USA) 3989 Contemporary Mathematics, vol. 339, 1991, pp. 85-94,

[14]

N. Immerman, Descriptive Complexity, Springer, New York, NY, 1999.

[15]

D.S. Johnson, A catalog of complexity classes, in: J. Van Leeuwen (Ed.), Handbook of Theoretical, Computer Science Vol. A: Algorithms and Complexity, Elsevier Science Publishers, Amsterdam. 1990, pp. 67-161.

Digital Library

[16]

T.Y, Kong, On topology preservation in 2-D and 3-D thisming. Internat. J. Pattern Recognition Artificial Intelligence 9(5) (39-95) 813-844.

[17]

T.Y. Kong, A. Rosenfeld, Digital topology: introduction and survey, Comput. Vision Graphics lniagc Process. 48 (1989) 357-393.

Digital Library

[18]

A. Lenoir, R. Matgouyres, M. Revenu, Fast computation of the normal vector field of the surface of3D discrete object, DGCI'96, Lecture Notes in Computer Science, vol. 3176, Springer, Lyon, France. November 1996, pp. 101-112.

Digital Library

[19]

A. Lenoir, Fast estimation of mean curvature on the surface of a 3D discrete object, DGCI'97, Lecture Notes in Computer Science. vol. 1347, December 1997, pp. 175-186.

Digital Library

[20]

S. Lindell, A Logspace Algorithm for Tree Canonization, Proc. 24th ACM Symp, on Theory of Computing ACM Press, 1992, pp. 400-404.

Digital Library

[21]

R. Malgouyres, Homotopy in 2-dimensional digital images, Theoret. Comput. Sci. 230 (2000) 221-233.

Digital Library

[22]

R. Malgouyres, A. Lenoir, Topology preservation within digital surfaces, Graphical Models (GMIP) 62 (2000) 71-84.

Digital Library

[23]

C.H. Papadimitnou Computational Complexity AddisonWesley, Reading, MA, 1994.

[24]

C. Ronse, A topological characterization of thinning, Theoret. CO-Put. Set. 43 (1986) 31-41.

Digital Library

[25]

A. Rosenfeld, Adjacency in digital pictures, Infona. and Control 26 (1974) 24-33.

[26]

A. Rosenfeld T.Y. Kong, A. Nakamura, Topology-Preserving deformations of two-valued digital pictures Graphical Models Image Process, 60 (I) (1998) 24-34.

Digital Library

[27]

H. Saubing, Finite Automata Formal Logic and Circuit Complexity, Birduser Boston, 1994.

Digital Library

[28]

J.K. Udupa, Multidimensional digital boundaries CVGIP: Graphical Models Image Process. 56 (4) (1994) 311-323.

Digital Library

Cited By

Asano T(2012)In-place Algorithm for Erasing a Connected Component in a Binary ImageTheory of Computing Systems10.5555/2556794.255777150:1(111-123)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2556794.2557771
Asano T(2010)Do we need a stack to erase a component in a binary image?Proceedings of the 5th international conference on Fun with algorithms10.5555/1875616.1875620(16-27)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1875616.1875620
Asano TBrimkov VBarneva R(2009)Some theoretical challenges in digital geometryDiscrete Applied Mathematics10.1016/j.dam.2009.04.022157:16(3362-3371)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.dam.2009.04.022
Show More Cited By

Index Terms

On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Planar and Grid Graph Reachability Problems
Special Issue: Computation and Logic in the Real World; Guest Editors: S. Barry Cooper, Elvira Mayordomo and Andrea Sorbi
We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for $\mathsf{NL}$. In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main ...
Homotopy Properties of Sphere-Like Digital Images

Recent papers have discussed digital versions of the classical fundamental group for digital images. It has been shown that for non-contractible digital simple closed curves, the digital fundamental group is isomorphic to the integers, in analogy with ...
Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 283, Issue 1

June 11 2002

304 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 11 June 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Asano T(2012)In-place Algorithm for Erasing a Connected Component in a Binary ImageTheory of Computing Systems10.5555/2556794.255777150:1(111-123)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2556794.2557771
Asano T(2010)Do we need a stack to erase a component in a binary image?Proceedings of the 5th international conference on Fun with algorithms10.5555/1875616.1875620(16-27)Online publication date: 2-Jun-2010
https://dl.acm.org/doi/10.5555/1875616.1875620
Asano TBrimkov VBarneva R(2009)Some theoretical challenges in digital geometryDiscrete Applied Mathematics10.1016/j.dam.2009.04.022157:16(3362-3371)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.dam.2009.04.022
Asano T(2009)Constant-Working-Space Algorithms for Image ProcessingEmerging Trends in Visual Computing10.1007/978-3-642-00826-9_12(268-283)Online publication date: 16-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00826-9_12

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents