I will describe recent work (SODA '02) by S. Arya and T. Malamatos.
They describe a data structure based on well-separated pair decompositions
which improves on previous size bounds. The approximate Voronoi diagram can
be used for answering approximate nearest neighbor queries.