We present alternate reductions of the nearest neighbor searching problem to Point Location in Balls that reduces the space bound of Sariel Har-Peled's [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] recent result on Approximate Voronoi Diagrams to linear while maintaining the logarithmic search time. We do this by simplifying the construction of [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] that reduces the number of balls generated by algorithm 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. The construction of our data structures takes O (n log n) time. © 2006 Elsevier Inc. All rights reserved.