Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions

Abstract

Our proposed solutions to the nearest neighbour searching problem for Point Location in Balls are an alternative to Sariel Har-Peled's recent work on Approximate Voronoi Diagrams, which maintains the logarithmic search time, and reduces the space bound to linear. This work is published in the Proc. of IEEE FOCS in 2001 and can be accessed online at http://www.uiuc.edu/~sariel/papers. We achieve this by streamlining the building of the algorithm that reduces the number of balls generated by it to O(n log n), as described in [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc. edu/sariel/papers]. In order to accomplish linear space decomposition for closest neighbour searches, we further decrease the ball count by introducing a novel hierarchical decomposition strategy and expanding upon PLEBs. Our data structures are constructed with a temporal complexity of O(n log n).