  We study the k nearest neighbors problem in the plane for general, convex,
pairwise disjoint sites of constant description complexity such as line
segments, disks, and quadrilaterals and with respect to a general family of
distance functions including the L_p-norms and additively weighted Euclidean
distances. For point sites in the Euclidean metric, after four decades of
effort, an optimal data structure has recently been developed with O( n )
space, O( log n + k ) query time, and O( n log n ) preprocessing time. We
develop a static data structure for the general setting with nearly optimal O(
n log log n ) space, the optimal O( log n + k ) query time, and expected O( n
polylog n ) preprocessing time. The O( n log log n ) space approaches the
linear space, whose achievability is still unknown with the optimal query time,
and improves the so far best O( n ( log^2 n )( log log n )^2 ) space of Bohler
et al.'s work. Our dynamic version (that allows insertions and deletions of
sites) also reduces the space of Kaplan et al.'s work from O( n log^3 n ) to O(
n log n ).
  To obtain these progresses, we devise shallow cuttings of linear size for
general distance functions. Shallow cuttings are a key technique to deal with
the k nearest neighbors problem for point sites in the Euclidean metric.
Agarwal et al. already designed linear-size shallow cuttings for general
distance functions, but their shallow cuttings could not be applied to the k
nearest neighbors problem. Recently, Kaplan et al. constructed shallow cuttings
that are feasible for the k nearest neighbors problem, while the size of their
shallow cuttings has an extra double logarithmic factor. Our innovation is a
new random sampling technique for the analysis of geometric structures. Since
our new technique provides a new way to develop and analyze geometric
algorithms, we believe it is of independent interest.
