Geometry of Locally Finite Spaces


The book presents a self-contained theory of locally finite spaces including a set of new axioms, numerous definitions and theorems concerning the properties of that spaces. It also presents a way of defining digital geometry in locally finite spaces independently of Euclidean geometry. A large portion of the book is devoted to applications to computer imagery.

Locally finite spaces give the possibility to overcome the existing discrepancy between theory and applications: The traditional way of research consists in making theory in Euclidean space with real coordinates while applications deal only with finite discrete sets and rational numbers. The reason is that even the smallest part of the Euclidean space cannon be explicitly represented in a computer and computations with irrational numbers are impossible since there exists no arithmetic of irrational numbers.

Locally finite spaces are on the one hand theoretically consistent and conform with classical topology and on the other hand explicitly representable in a computer. Coordinates are rational or integer numbers.

New data structures and numerous geometric and topological algorithms are presented. Most algorithms are accompanied by a pseudo-code based on the C++ programming language.




“It is a real pleasure to read the book. I will recommend it to several people and libraries, because it continues to tell to young researchers that topology of cell complexes is not only the best way for the theory, especially for multicolor images, but also the only practical topology for programming large scale software.”.

Jean Françon, Professor em., University Louis Pasteur, France



"It is certainly an impressive work. Much of what it covers cannot be found in any other book that I know of. The book will be an important reference for me and, I believe, for anyone else who has a serious interest in digital geometry. I expect to make much use of it in the future.

T. Yung Kong, Professor of Computer Science, City University of New York."



“The author has developed a new theory and proved numerous theorems concerning the properties of locally finite spaces. The book, being the first one it its own way, is addressed to specialists in digital topology and digital geometry. It is important for them”.

S. V. Matveev, Professor of Chelyabinsk State University, Corresponding member of Russian Academy of Sciences



1    Introduction

1.1    About the Development of the Locally Finite Topology

1.2    Contents of the Monograph

1.3    The Aims of the Monograph

2    Axiomatic Approach to Digital Topology

2.1    Why Do We Introduce a New Set of Axioms

2.2    Axioms of Digital Topology

2.3    Relation between the Suggested and Classical Axioms

2.4    Deducing the Properties of ALF Spaces from Axioms

2.5    Previous Work

3    Theory of Abstract Cell Complexes

3.1 Topology of Complexes

3.2    Cartesian Complexes and Combinatorial Coordinates

3.3    AC Complexes Compared with other Locally Finite Spaces

3.4 Combinatorial Homeomorphism, Balls and Spheres

3.5 Justification of the above Definitions

3.6 Definition of the Combinatorial Homeomorphism

3.7 Generalized Boundary and Boundary of a Space

3.8 Orientation of AC Complexes

3.9 Combinatorial Manifolds

3.10  Block Complexes

3.11 Consistency of (m, n)-Adjacencies

3.12 Completely Connected Spaces

3.13 Problems to Be Solved



4    Mappings among Locally Finite Spaces

4.1    Connectedness-Preserving Correspondences (CPM)

4.2    CPMs and Combinatorial Homeomorphism

4.3    Some Properties of Manifolds and of Block Complexes

4.4    Problems to Be Solved

5    Interlaced Spheres in Locally Finite Spaces

5.1    Preface

5.2    Interlaced Multidimensional Spheres

5.3    Examples of Interlaced Spheres

6    Digital Geometry based on Topology of Complexes

6.1    Preface

6.2    Classification of Digital Curves

6.3    Introduction to Digital Analytical Geometry

7    Linear Inequalities in Locally Finite Spaces

7.1   Digital Collinearity, Half-Spaces and Convex Sets

7.2   Digital Straight Segments (DSS)

7.3   Theory of Digital Plane Patches

8    Surfaces in a Three-Dimensional Space

8.1    Introduction

8.2    Frontiers of Sets of Voxels

8.3    Quasi-Manifolds and Their Properties

8.4    Adjacency of Principal Cells of a Quasi-Manifold

9    Digital Arcs and Their Recognition

9.1    Some Definitions

9.2    Recognition of Digital Arcs

10    Data Structures

10.1  The Standard Grid

10.2  The Combinatorial Grid




10.3  Data Structures Using Lists of Space Elements

10.4  The Two-Dimensional Cell List

10.5  The Three-Dimensional Cell List

11    Applications and Algorithms

11.1  Recommendations for Applications

11.2  Tracing Boundaries in 2D Images and 2D Subspaces

11.3  Encoding of DSSs with Additional Parameters

11.4  Reconstruction of Multidimensional Images from Boundaries

11.5  Labeling Connected Component in an nD Space

11.6  Skeletons of Subsets in a Two-Dimensional Space

11.7  Algorithms for Topological Investigations

11.8  Conclusion of Section 11 and Problems to Be Solved

12    Convex Hulls in a Three-Dimensional Space

12.1  Introduction

12.2  The Algorithm

12.3  Proof of Correctness

12.4  Results of Computer Experiments

13    Algorithms for Tracing and Encoding of Surfaces

13.1  Introduction

13.2  The Depth-First Method

13.3  Euler Circuits

13.4  Spiral Tracing

13.5  The Economical Hoop Code

13.6  Problems to Be Solved

14   Topics for Discussion

14.1  Real Numbers and Derivatives

14.2  Inference of the Taylor Formula for Finite Differences

References; Index



About the author


Vladimir A. Kovalevsky received his diploma in physics from the Kharkov University (Ukraine) in 1950, the first doctoral degree in technical sciences from the Central Institute of Metrology (Leningrad) in 1957, and the second doctoral degree in computer science from the Institute of Cybernetics of the Academy of Sciences of the Ukraine (Kiev) in 1968. From 1961 to 1983 he served as Head of Department of Pattern Recognition at that Institute.

He has been living  in Germany since 1983. From 1983 to 1989 he was researcher at the Central Institute of Cybernetics of the Academy of Sciences of the GDR, Berlin. From 1989 to 2004 he was professor of computer science at the University of Applied Sciences Berlin with an interruption for three years (1998-2001). In that time he was scientific collaborator at the University of Rostock. He worked as visiting researcher at the University of Pennsylvania (1990), at the Manukau Institute of Technology, New Zeeland (2005) and as lecturer at the Chonbuk National University, South Korea (2009).

He has been plenary speaker at conferences in Europe, America and New Zeeland. His research interests include digital geometry, digital topology, computer vision, image processing and pattern recognition. He has published four monographs and more than 180 journal and conference papers in image analysis, digital geometry and digital topology.






Vladimir A. Kovalevsky

Geometry of Locally Finite Spaces


A self-contained theory with axioms,

definitions and theorems as well as numerous algorithms for computer imagery


330 pages, 120 figures (12 in color), 85 literature references

Soft cover: € 27.50; (sold out).

Foil cover: € 32.30;

ISBN  978-3-9812252-0-4  



The author:

Vladimir A. Kovalevsky




© 2008 Publishing House  Dr. Baerbel Kovalevski

Heisterbachstrasse 23 B, 12559 Berlin, Germany


To ordered the book send your name and mailing address to fax +49-30-659-08-707 or click to:

E-mail to the Publishing House




You will obtain the book with an invoice for remitting the price + postage