https://scholars.lib.ntu.edu.tw/handle/123456789/624632
標題: | Nearly optimal planar K nearest neighbors queries under general distance functions | 作者: | CHIH-HUNG LIU | 公開日期: | 2020 | 卷: | 2020-January | 起(迄)頁: | 2842-2859 | 來源出版物: | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | 摘要: | 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 Lp-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(nlog n) preprocessing time [1, 17]. We develop a static data structure for the general setting with nearly optimal O(nlog log n) space, the optimal O(log n+k) query time, and expected O(n polylog n) preprocessing time. The O(nlog 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(log2 n)(log log n)2) space of Bohler et al.'s work [12]. Our dynamic version (that allows insertions and deletions of sites) also reduces the space of Kaplan et al.'s work [29] from O(nlog3 n) to O(nlog n) while keeping O(log2 n + k) query time and O(polylog n) update time, thus improving many applications such as dynamic bichromatic closest pair and dynamic minimum spanning tree in general planar metric, and shortest path tree and dynamic connectivity in disk intersection graphs. 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. [4] 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. [29] 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. While our shallow cuttings seem, to some extent, merely a simple transformation of Agarwal et al.'s [4], the analysis requires our new technique to attain the linear size. Since our new technique provides a new way to develop and analyze geometric algorithms, we believe it is of independent interest. Copyright © 2020 by SIAM |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85084038349&partnerID=40&md5=853302ef2de29979c02651c265b3b12b https://scholars.lib.ntu.edu.tw/handle/123456789/624632 |
SDG/關鍵字: | Data structures; Linear transformations; Motion compensation; Structural optimization; Trees (mathematics); Description complexity; Geometric algorithm; Geometric structure; Insertions and deletions; Intersection graph; K-nearest neighbors; Minimum spanning trees; Weighted euclidean distance; Nearest neighbor search |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。