Geometry of Locally Finite Spaces


by Vladimir A. Kovalevsky

 Publishing House Dr. Baerbel Kovalevski, 2008


Reviewed by:  Petra Wiederhold (Mexico)

Click here for Top of Page

The monograph by Professor Vladimir Kovalevsky presents an original self-contained  digital approach to Topology and Geometry for modelling discrete sets, as appearing in Digital Image Processing and Analysis, and in Computer Graphics. The book is based on research of the author within theoretical and algorithmic aspects of digital topology and digital geometry during the last thirty years. The work not only assembles all contributions made by the author into a unique context, where methods and algorithms are consequently founded by and deduced from the theoretical base, but also extends previous investigations, presenting new definitions and theorems and new efficient algorithms for digital image processing and analysis.

The book is clearly written, well structured, and contains numerous good illustrations. In my opinion, it can serve as a textbook for teaching and guiding  students, as well as a study base or reference book for researchers. I think, it is of interest for anyone interested in digital topology, digital geometry and computer imagery, but also in other fields where discrete sets are of importance.

The book is an important contribution to the development of a self-contained digital topology and geometry, whose necessity has been recognized by numerous authors. Pioneering proposals for digital topology and geometry were those based on graph theory, for example by the school of Rosenfeld. These models, at their origin, analogously as in the development of a topological space, start with describing local nearness, considering together with each space element, some neighborhood of it. Nevertheless, these models do not provide a topological space which is distinct from the discrete one, where all subsets are open, and which (as a topological space) is totally disconnected. Kovalevsky’s approach is based on the construction of a topological locally finite T0 Alexandroff space, which is related to posets (partially ordered sets) and to the cell complexes from combinatorial topology. This approach has been named by other authors the topological approach to digital topology. Kovalevsky develops geometrical concepts within cell complexes, and finally, the whole theoretical base is consequently applied to develop algorithms for digital image processing and analysis.

The 330-page book is subdivided into 14 chapters. The introductory chapter presents a short retrospect to the origin of the book followed by an overview of the contents and of the pursued aims.

In Chapter 2, Kovalevsky presents an interesting and original axiomatic way to deduce from suppositions "which are natural from the point of view of our intuition and of practical demands" (page 7) that a space suitable for describing topology in discrete sets, has to be a locally finite non-discrete topological space, which turns out to be a T0 Alexandroff space. The construction starts with a locally finite Fréchet space (a set with a local neighborhood system, which not necessarily defines a topological space), named here LF space. Kovalevsky proves that under the imposition of four axioms, where the concept of frontier plays a central role, that the neighborhood system of a LF space, named then ALF space, generates a T0 non-T1 Alexandroff space.

Chapter 3 is devoted to a detailed treatment of basics and topological properties of abstract cell complexes, defined as ALF spaces equipped with a local monotone dimension function. In particular, K-complexes are described, where the dimension function is the poset dimension known from lattice theory.  Here we find interesting proposals of definitions of balls and spheres, without reference to any metric or to the Euclidean space, of combinatorial homeomorphisms based on elementary subdivisions of cells, of generalized notions of boundary, and of the orientation of abstract complexes. Most concrete algorithms presented in the book work on a special class of abstract cell complexes named cartesian complexes. Such a cartesian complex corresponds to an Alexandroff space which is homeomorphic to a cartesian product of bounded segments (probably of distinct length in each “coordinate axis”) of the Khalimsky line. This chapter also investigates combinatorial manifolds, and analyzes (m,n)-adjacencies due to Kong.

Chapter 4 considers a new approach to maps among ALF spaces, similar to continuous maps and homeomorphism, which turn out to be isomorphism between complexes. Kovalevsky suggests to use connectedness preserving correspondences (CPMs) which can map one space element to many elements, instead of single-valued functions. He shows that a combinatorial homeomorphism based on elementary subdivisions of space elements uniquely defines a continuous CPM whose inverse is also continuous. Chapter 5 investigates some problems concerning interlaced (interlinked) spheres of different dimensions in n-dimensional cell complexes.

Chapters 6 to 9 are devoted to the development of digital geometry. The author motivates and claims that all geometrical concepts in this book are independent of Euclidean geometry, and that "geometry must be constructed in a topological space which must be completely defined before starting with the construction of geometry. Such a topological space is an abstract cell complex .. " (page 107) . Arithmetics on cell complexes is introduced as on the rationals, and collinearity and convexity are carefully handled by using inequalities and arithmetics within rationals. However, when dealing with rotation as an isometry, Kovalevsky says, "It is easily seen that the only suitable metric is the Euclidean one. It is of course possible to employ Euclidean metric in a space which is not the Euclidean one!" (page 114). Well, at this point I felt "And here, poor fool! with all my lore, I stand, no wiser than before" [F], because, then, geometry has nothing to do with the topological space just constructed before. Actually, any metric would have this effect, because it would generate a Hausdorff topology which definitively cannot be the Alexandroff topology of our complex.  Chapter 7 is devoted to digital straight segments (DSS) in two-dimensional complexes, which are consequently considered as one-dimensional complexes, and using rational calculus, and to digital plane patches (DPP) in three-dimensional complexes. (We recall, however, that DSS and DPP were invented in order to estimate geometrical properties of Euclidean objects, under the multi-grid convergence requirement, which has a strong relation to the Euclidean space). Chapter 8 deals with surfaces and manifolds, Chapter 9 with digital circular arcs.

In Chapters 10 to 13, Kovalevsky presents numerous algorithms for digital image processing, analysis, compression, and reconstruction from decodings, based on the modelling of (the domain of) digital images by cell complexes, many of them in full detail, with examples and C++-pseudocodes, others by presenting the main ideas. Data structures for handling the cell complexes in the computer are described, too, as well as ideas for visualization.  Some chapters of the book contain problems to be solved that will stimulate further research. Additionally, Chapter 14 presents additional topics for discussion, containing ideas and questions about avoiding the usage of irrational numbers.

In conclusion, Kovalevsky’s book is interesting and important, and I am sure that it will have to be studied seriously. However, I would like to note that it could have been even more integrated in the context of actual research. For example, although deduced or motivated in other ways as by Kovalevsky, parts of the topological approach to topology and geometry, have been independently developed by other authors; for example by Khalimsky, Kopperman, Meyer, Kong, (Julian) Webster, Kronheimer, to mention just a few. Various works, strongly related to the topological approach to digital topology, are not mentioned or cited in Kovalevsky’s book. We have also no mention of Gabor Herman’s book "Geometry of Digital Spaces“ (Birkhäuser Boston, USA, 1998), and of the works of Li Chen, in relation to the modelling of surfaces. The reader of Kovalevsky’s book can get the impression that the topological approach is the unique reasonable one to develop digital topology. Nevertheless, recently several new investigation lines have appeared within the development of digital topology and geometry, based on structures distinct from graphs and topological spaces, for example, on lattices, domains and matroids.

With respect to the importance of Kovalevsky’s book, remember that Computer Science is not the only field interested in such digital models. Topology and Geometry, since their beginnings, have had as one principal aim to describe the earth and universe. At the moment that Newton invented the infinitesimal calculus in order to find good approximations for the calculation of tremendous expressions of sums and differences, continuous models as (locally) Euclidean spaces, began their triumphal procession for describing reality. Today we don’t know if a continuous or a digital space should model the universe; surely each of them describes distinct aspects of reality. On our way that we “may detect the innermost force which binds the world, and guides its course” [F], we are just at the beginning.


[F] J.W.v. Goethe, Faust, First Part of the Tragedy, Scene “Night” (Faust's Monologue), 1808.

Click above to go to the author's web page where you can read the abstract, see the Table of Contents, read about the author, and get ordering information.

Right Arrow: Next
Right Arrow: Previous

Book Reviews Published in

the IAPR Newsletter


Close Range Photogrammetry:  Principles, Methods, and Applications

by Luhmann, Robson, Kyle, and Harley

             (see review in this issue)


Classification and Learning Using Genetic Algorithms: Applications in Bioinformatics and Web Intelligence

by  Bandyopadhyay and Pal

             (see review in this issue)


Learning Theory:

An Approximation Theory Viewpoint

by Cucker and Zhou

             (see review in this issue)


Character Recognition Systems—A Guide for Students and Practitioners

by Cheriet, Kharma, Liu, and Suen

             (see review in this issue)


Machine Learning in Document Analysis and Recognition

by Marinai and  Fujisawa (Editors)

             (see review in this issue)


From Gestalt Theory to Image Analysis—A Probabilistic Approach

By Desolneux, Moisan, and Morel

             (see review in this issue)


Numerical Recipes:  The art of scientific computing, 3rd ed.

by Press, Teukolsky, Vetterling and Flannery

             Jul ‘08    [html]     [pdf]


Feature Extraction and Image Processing, 2nd ed.

by Nixon and Aguado

             Jul ‘08    [html]     [pdf]


Digital Watermarking and Steganography:

Fundamentals and Techniques

by Shih

             Jul ‘08    [html]     [pdf]


Springer Handbook of Speech Processing

by Benesty, Sondhi, and Huang, eds.

             Jul ‘08    [html]     [pdf]


Digital Image Processing: An Algorithmic Introduction Using Java

by Burger and Burge

             Jul ‘08    [html]     [pdf]


Bézier and Splines in Image Processing and Machine Vision

by Biswas and Lovell

             Jul ‘08    [html]     [pdf]


Practical Algorithms for Image Analysis, 2 ed.

by  O’Gorman, Sammon and Seul

             Apr ‘08   [html]     [pdf]


The Dissimilarity Representation for Pattern Recognition:  Foundations and Applications

by Pekalska and Duin

             Apr ‘08   [html]     [pdf]


Handbook of Biometrics

by Jain, Flynn, and Ross (Editors)

             Apr ‘08   [html]     [pdf]


Advances in Biometrics –

Sensors, Algorithms, and Systems

by Ratha and Govindaraju, (Editors)

             Apr ‘08   [html]     [pdf]


Dynamic Vision for Perception and Control of Motion

by Dickmanns

             Jan ‘08   [html]     [pdf]



by Polanski and Kimmel

             Jan ‘08   [html]     [pdf]


Introduction to clustering large and high-dimensional data

by Kogan

             Jan ‘08   [html]     [pdf]


The Text Mining Handbook

by Feldman and Sanger

             Jan ‘08   [html]     [pdf]


Information Theory, Inference,

and Learning Algorithms

by Makay

             Jan ‘08   [html]     [pdf]


Geometric Tomography

by Gardner

           Oct ‘07   [html]     [pdf]


“Foundations and Trends in Computer Graphics and Vision”

Curless, Van Gool, and Szeliski., Editors

           Oct ‘07   [html]     [pdf]


Applied Combinatorics on Words

by M. Lothaire

           Jul ‘07    [html]     [pdf]



Human Identification Based on Gait

by Nixon, Tan and Chellappar

             Apr ‘07   [html]     [pdf]


Mathematics of Digital Images

by Stuart Hogan

             Apr ‘07   [html]     [pdf]


Advances in Image and Video Segmentation

Zhang, Editor

             Jan ‘07 [html]      [pdf]


Graph-Theoretic Techniques for Web Content Mining

by Schenker, Bunke, Last and Kandel

             Jan ‘07 [html]      [pdf]


Handbook of Mathematical Models in Computer Vision

by Paragios, Chen, and Faugeras (Editors)

           Oct ‘06     [html]     [pdf]


The Geometry of Information Retrieval

by van Rijsbergen

           Oct ‘06     [html]     [pdf]


Biometric Inverse Problems

by Yanushkevich, Stoica, Shmerko and Popel

           Oct ‘06     [html]     [pdf]


Correlation Pattern Recognition

by Kumar, Mahalanobis, and Juday

           Jul. ‘06     [html]     [pdf]


Pattern Recognition 3rd Edition

by Theodoridis and Koutroumbas

           Apr. ‘06    [html]     [pdf]


Dictionary of Computer Vision and

Image Processing

by R.B. Fisher, et. Al

           Jan. ‘06    [html]     [pdf]


Kernel Methods for Pattern Analysis

by Shawe-Taylor and Cristianini

           Oct. ‘05    [html]     [pdf]


Machine Vision Books

           Jul. ‘05     [html]     [pdf]


CVonline:  an overview

           Apr. ‘05    [html]     [pdf]


The Guide to Biometrics by Bolle, et al

           Jan. ‘05    [html]     [pdf]


Pattern Recognition Books

           Jul. ‘04                  [pdf]