LIPIcs.SoCG.2018.73.pdf
- Filesize: 0.67 MB
- 14 pages
Document
New Bounds for Range Closest-Pair Problems
Authors
-
Part of:
Volume:
34th International Symposium on Computational Geometry (SoCG 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-08
Cite As Get BibTex
Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New Bounds for Range Closest-Pair Problems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.73
Abstract
Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.
Subject Classification
Keywords
- Closest-pair
- Range search
- Candidate pairs
- Average-case analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, and Michiel Smid. On the power of the semi-separated pair decomposition. In Workshop on Algorithms and Data Structures, pages 1-12. Springer, 2009.
-
Pankaj K Agarwal, Jeff Erickson, et al. Geometric range searching and its relatives. Contemporary Mathematics, 223:1-56, 1999.
-
M. de Berg, M. van Kreveld, M. Overmars, and O. C. Schwarzkopf. Computational geometry. In Computational geometry, pages 1-17. Springer, 2000.
-
Herbert Edelsbrunner, Leonidas J Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317-340, 1986.
-
Prosenjit Gupta. Range-aggregate query problems involving geometric aggregation operations. Nordic journal of Computing, 13(4):294-308, 2006.
-
Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, and Michiel Smid. Data structures for range-aggregate extent queries. Computational Geometry: Theory and Applications, 2(47):329-347, 2014.
-
Saladi Rahul and Yufei Tao. On top-k range reporting in 2D space. In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 265-275. ACM, 2015.
-
Neil Sarnak and Robert E Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669-679, 1986.
-
Jing Shan, Donghui Zhang, and Betty Salzberg. On spatial-range closest-pair query. In International Symposium on Spatial and Temporal Databases, pages 252-269. Springer, 2003.
-
R Sharathkumar and Prosenjit Gupta. Range-aggregate proximity queries. IIIT Hyderabad, Telangana, 500032, 2007.
-
Michiel Smid. Closest point problems in computational geometry. Citeseer, 1995.
-
Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New bounds for range closest-pair problems. arXiv preprint arXiv:1712.09749, 2017.