Constant time neighbor finding in quadtrees: An experimental result

Neighbor finding is an important and a basic part of image processing in quadtrees. A constant time algorithm is proposed for neighbor finding in quadtrees in [1]. In this paper, empirical tests are given for the constant time algorithm in comparison with usual neighbor finding algorithm using quadtrees [2] and another constant time algorithm using linear quadtree [3]. Experiments using synthetic images simulating worst case situations show that the proposed algorithm is in constant time complexity while others are not. Even for experiments using natural images, the proposed algorithm is more than twice as fast as algorithm using quadtrees and is slightly as fast as algorithm using linear quadtrees.