https://scholars.lib.ntu.edu.tw/handle/123456789/624628
Title: | NEARLY OPTIMAL PLANAR K NEAREST NEIGHBORS QUERIES UNDER GENERAL DISTANCE FUNCTIONS | Authors: | CHIH-HUNG LIU | Keywords: | computational geometry; general distance functions; k nearest neighbors searching; randomized algorithms; randomized data structures; range searching; shallow cuttings | Issue Date: | 2022 | Journal Volume: | 51 | Journal Issue: | 3 | Start page/Pages: | 723-765 | Source: | SIAM Journal on Computing | Abstract: | 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 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 Mathematics |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85133185008&doi=10.1137%2f20M1388371&partnerID=40&md5=fe2f8144a8458232297f783531c81886 https://scholars.lib.ntu.edu.tw/handle/123456789/624628 |
ISSN: | 00975397 | DOI: | 10.1137/20M1388371 | SDG/Keyword: | Data 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 geometry |
Appears in Collections: | 電機工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.