Abstract
Many applications of digital image processing now deal with three- and higher-dimensional images. One way to represent n-dimensional digital images is to use the specialization graphs of subspaces of the Alexandroff topological space ℤn (where ℤ denotes the integers with the Khalimsky line topology). In this paper the dimension of any such graph is defined in three ways, and the equivalence of the three definitions is established. Two of the definitions have a geometric basis and are closely related to the topological definition of inductive dimension; the third extends the Alexandroff dimension to graphs. Diagrams are given of graphs that are dimensionally correct discrete models of Euclidean spaces, n-dimensional spheres, a projective plane and a torus. New characterizations of n-dimensional (digital) surfaces are presented. Finally, the local structure of the space ℤn is analyzed, and it is shown that ℤn is an n-dimensional surface for all n≥1.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P.S. Alexandroff, “Diskrete Räume,” Mat. Sb., Vol. 1, pp. 501–519, 1937.
G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove, and D.S. Scott, A Compendium of Continuous Lattices, Springer-Verlag: Berlin, 1980.
A.V. Ivashchenko, “Contractible transformations do not change the homology groups of graphs,” Discrete Math., Vol. 126, pp. 159–170, 1994.
A.V. Ivashchenko, “Dimension on discrete spaces,” International Journal of Theoretical Physics, to appear in August 1994.
A.V. Ivashchenko, “Representation of smooth surfaces by graphs. Transformations of graphs which do not change the Euler characteristic of graphs,” Discrete Math., Vol. 122, pp. 219–233, 1993.
A.V. Ivashchenko, “Homology groups on molecular spaces and graphs,” abstract, 8th Summer Conference on General Topology and Applications, New York, USA, 1992.
E. Halimski (E. Khalimsky), Uporiadochenie Topologicheskie Prostranstva (Ordered Topological Spaces), Naukova Dumka, Kiev, 1987.
E. Khalimsky, “Pattern analysis of N-dimensional digital images,” in Proceedings, 1986 IEEE International Conference on Systems, Man and Cybernetics CH2364-8/86, pp. 1559–1562, 1986.
E. Khalimsky, “Topological structures in computer science,” J. Appl. Math. Simulation, Vol. 1, pp. 25–40, 1987.
E. Khalimsky, R. Kopperman, and P. Meyer, “Computer graphics and connected topologies on finite ordered sets,” Topology and Applications, Vol. 36, pp. 1–17, 1990.
T.Y. Kong and E. Khalimsky, “Polyhedral analogs of locally finite topological spaces,” in General Topology and Applications: Porceedings 1988 Northeast Conference, Marcel Dekker: NY, pp. 153–164, 1990.
T.Y. Kong and A. Rosenfeld, “Digital topology: Introduction and survey,” Comput. Vision Graphics Image Process, Vol. 48, pp. 357–393, 1989.
T.Y. Kong, R. Kopperman, and P.R. Meyer, “A topological approach to digital topology,” Amer. Math. Monthly, Vol. 98, pp. 901–917, 1991.
R. Kopperman, P. Meyer, and R. Wilson, “A Jordan surface theorem for three-dimensional digital space,” Discrete Comput. Geom., Vol. 6, pp. 155–161, 1991.
V.A. Kovalevsky, “Finite topology as applied to image analyses,” Comput. Vision Graphics Image Process, Vol. 46, pp. 141–161, 1989.
A. Rosenfeld, “Connectivity in digital pictures,” J. Assoc. Comput. Mach., Vol. 17, pp. 146–160, 1970.
A. Rosenfeld, “Digital topology,” Amer. Math. Monthly, Vol. 86, pp. 621–630, 1979.
R. Sorkin, “Finitary substitute for continuous topology,” International Journal of Theoretical Physics, Vol. 30, pp. 923–947, 1991.
P. Wiederhold and R. Wilson, “Dimension for Alexandrov Spaces,” in Vision Geometry, Robert A. Melter and Angela Y. Wu (Eds.), Proc. SPIE 1832, pp. 13–22, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Evako, A.V., Kopperman, R. & Mukhin, Y.V. Dimensional properties of graphs and digital spaces. J Math Imaging Vis 6, 109–119 (1996). https://doi.org/10.1007/BF00119834
Issue Date:
DOI: https://doi.org/10.1007/BF00119834