Header menu link for other important links
Nearest neighbors search using point location in Balls with applications to Approximate Voronoi Decompositions
Y. Sabharwal, N. Sharma,
Published in Springer Verlag
Volume: 2556 LNCS
Pages: 311 - 323
We present improved reductions of the nearest neighbor searching problem to Point Location in Balls by constructing linear size Approximate Voronoi Diagrams while maintaining the logarithmic search time. We do this first by simplifying the construction of Har-Peled[9] that reduces the number of balls generated by a logarithmic factor to O(n log n). We further reduce the number of balls by a new hierarchical decomposition scheme and a generalization of PLEBs to achieve linear space decomposition for nearest neighbor searching. © Springer-Verlag Berlin Heidelberg 2002.
About the journal
Published in Springer Verlag
Open Access
Impact factor