Search

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. [ABSTRACT FROM AUTHOR]