Document Open Access Logo

New Bounds for Range Closest-Pair Problems

Authors Jie Xue, Yuan Li, Saladi Rahul, Ravi Janardan

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2018.73.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Closest-pair
  • Range search
  • Candidate pairs
  • Average-case analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Jie Xue
Yuan Li
Saladi Rahul
Ravi Janardan

References

  1. 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. Google Scholar
  2. Pankaj K Agarwal, Jeff Erickson, et al. Geometric range searching and its relatives. Contemporary Mathematics, 223:1-56, 1999. Google Scholar
  3. M. de Berg, M. van Kreveld, M. Overmars, and O. C. Schwarzkopf. Computational geometry. In Computational geometry, pages 1-17. Springer, 2000. Google Scholar
  4. Herbert Edelsbrunner, Leonidas J Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317-340, 1986. Google Scholar
  5. Prosenjit Gupta. Range-aggregate query problems involving geometric aggregation operations. Nordic journal of Computing, 13(4):294-308, 2006. Google Scholar
  6. 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. Google Scholar
  7. 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. Google Scholar
  8. Neil Sarnak and Robert E Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29(7):669-679, 1986. Google Scholar
  9. 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. Google Scholar
  10. R Sharathkumar and Prosenjit Gupta. Range-aggregate proximity queries. IIIT Hyderabad, Telangana, 500032, 2007. Google Scholar
  11. Michiel Smid. Closest point problems in computational geometry. Citeseer, 1995. Google Scholar
  12. Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New bounds for range closest-pair problems. arXiv preprint arXiv:1712.09749, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact