Publication Date:
2020-12-18
Description:
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.
Print ISSN:
0169-2968
Electronic ISSN:
1875-8681
Topics:
Computer Science
Permalink