We study k nearest neighbor queries in the plane for general ( convex, pairwise disjoint ) sites of constant description complexity ( such as line segment , disks, quadrilaterals and so on) and with respect to a general family of distance functions including the L_p-norms and constant-size convex distance functions. We develop a data structure with O( n log log n ) space,  O( log n + k ) query time, and expected O( n polylog n ) preprocessing time , removing a ( log^2 n log log n ) -factor from the O( n ( log^2 n )( log log n )^2 ) space of Bohler et al 's recent SoCG'16 work. In addition, our dynamic version (that allows insertions and deletions of sites) also improves the space of Kaplan et al.'s recent SODA'17 work from O( n log^3 n ) to O( n log n ) , and reduces a ( log^2 n )-factor from their deletion time. We obtain these improvements based on linear-size shallow cuttings , which are a standard technique to deal with the k nearest neighbor problem for point sites in the Euclidean metric. Kaplan et al. has generalized shallow cuttings to general distance functions, but the size of their version has an extra double logarithmic factor. We successfully design linear-size shallow cuttings for general distance functions, indicating that for general distance functions it could still be possible to achieve the same complexities as point sites in the Euclidean metric. Our breakthrough to achieve the linear size is a new random sampling technique (for the configuration space) that employs relatively many local conflicts to prevent relatively few global conflicts. We believe this new random sampling technique has its own merit for further applications .
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 .
R
k nearest neighbor queries
the k nearest neighbors problem
R
(
,
D
)
D
(
R
segment
segments
R
quadrilaterals and so on) and
and quadrilaterals and
R
constant-size convex distance functions.
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.
R
data structure with
static data structure for the general setting with nearly optimal
A
the optimal
R
, removing a ( log^2
. The O(
R
-factor from the
space approaches the linear space, whose achievability is still unknown with the optimal query time, and improves the so far best
R
's recent SoCG'16 work. In addition, our
.'s work. Our
R
improves
reduces
D
recent SODA'17
R
, and reduces a ( log^2 n )-factor from their deletion time. We obtain these improvements based on linear-size shallow cuttings , which are a standard
. To obtain these progresses, we devise shallow cuttings of linear size for general distance functions. Shallow cuttings are a key
R
neighbor
neighbors
R
Kaplan
Agarwal
R
has generalized shallow cuttings to
already designed linear-size shallow cuttings for
R
the
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
R
version
shallow cuttings
R
We successfully design linear-size shallow cuttings for general distance functions, indicating that for general distance functions it could still be possible to achieve the same complexities as point sites in the Euclidean metric. Our breakthrough to achieve the linear size
Our innovation
R
(for the configuration space) that employs relatively many local conflicts to prevent relatively few global conflicts. We believe this new random sampling technique has its own merit for further applications
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