CHIH-HUNG LIU2022-11-112022-11-11202200975397https://www.scopus.com/inward/record.uri?eid=2-s2.0-85133185008&doi=10.1137%2f20M1388371&partnerID=40&md5=fe2f8144a8458232297f783531c81886https://scholars.lib.ntu.edu.tw/handle/123456789/624628We 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 under a general family of distance functions including the Lp norms and additively weighted Euclidean distances. We compose a static data structure for this general setting with nearly optimal O(nlog log n) space, optimal O(log n + k) query time, and optimal expected O(nlog n) preprocessing time. We also devise a dynamic data structure (that allows insertions and deletions of sites) with O(nlog n) space, O(log2 n+klog n) query time, and expected amortized O(log2 n) insertion time and O(log4 n) deletion time, matching the best known time complexities for point sites in the Euclidean metric and improving many applications such as dynamic minimum spanning trees in a general planar metric and dynamic connectivity in disk intersection graphs. Our results, to some extent, indicate that for the k nearest neighbors problem, general distance functions may share the same time complexities with point sites in the Euclidean metric. To achieve this progress, we design vertical shallow cuttings of linear size for general distance functions. Vertical shallow cuttings are a key technique to tackle the k nearest neighbors problem for point sites in the Euclidean metric, while existing generalizations to general distance functions are either not vertical or not of linear size. Our innovation is a new random sampling technique for the analysis of geometric structures, and since this technique provides a new way to develop geometric algorithms, we believe it is of independent interest. © 2022 Society for Industrial and Applied Mathematicscomputational geometry; general distance functions; k nearest neighbors searching; randomized algorithms; randomized data structures; range searching; shallow cuttingsData structures; Membership functions; Motion compensation; Nearest neighbor search; Text processing; Trees (mathematics); Distance functions; Euclidean metrics; General distance function; K near neighbor searching; Nearest-neighbor searching; Query time; Randomized Algorithms; Randomized data structure; Range searching; Shallow cutting; Computational geometryjournal article10.1137/20M13883712-s2.0-85133185008