Before revision:  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.
After revision:  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 ) . 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 neighbor problem for point sites in the Euclidean metric.