Journal of Information Science and Engineering, Vol. 40 No. 2, pp. 245-251

Enumerating Furthest Pairs in Ultrametric Spaces

We prove the following results on enumerating or counting furthest pairs given an ultrametric space with n elements:

• There is a deterministic O(F + nlogn)-time algorithm for enumerating all furthest pairs, where F denotes the total number of furthest pairs.

• There is a Monte Carlo O(n/ε 2 )-time algorithm that estimates the number of furthest pairs to within a multiplicative factor in (1−ε,1+ε), where ε > 0. Furthermore, the time complexity of O(n/ε 2 ) cannot be improved to o(n · f(ε)) for any f(·).

Keywords:
ultrametric space, furthest pairs, combinatorial enumeration, counting, Monte Carlo algorithm