Affiliations: [a] Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Olshausenstraße 40, 24098 Kiel, Germany. [email protected], [email protected] | [b] Department of Computer Science, Brock University, St. Catharines, ON, Canada. [email protected]
Correspondence:
[†]
Address for correspondence: Department of Computer Science, Brock University, St. Catharines, ON, Canada.
Note: [*] The author gratefully acknowledges support from the Natural Sciences and Engineering Research Council of Canada (283267).
Abstract: Finite topological spaces and their dimensions have many applications in computer science, e.g., in digital topology, computer graphics and the analysis and synthesis of digital images. Georgiou et. al. [11] provided a polynomial algorithm for computing the covering dimension dim(X; 𝒯) of a finite topological space (X; 𝒯). In addition, they asked whether algorithms of the same complexity for computing the small inductive dimension ind(X; 𝒯) and the large inductive dimension Ind(X; 𝒯) can be developed. The first problem was solved in a previous paper [4]. Using results of the that paper, we also solve the second problem in this paper. We present a polynomial algorithm for Ind(X; 𝒯), so that there are now efficient algorithms for the three most important notions of a dimension in topology. Our solution reduces the computation of Ind(X; 𝒯), where the specialisation pre-order of (X; 𝒯) is taken as input, to the computation of the maximal height of a specific class of directed binary trees within the partially ordered set. For the latter an efficient algorithm is presented that is based on order- and graph-theoretic ideas. Also refinements and variants of the algorithm are discussed.
