New Bounds for Range Closest-Pair Problems

DOI10.4230/LIPICS.SOCG.2018.73zbMATH Open1464.68421arXiv1712.09749OpenAlexW2963732759MaRDI QIDQ5116533FDOQ5116533

Saladi Rahul, Jie Xue, Yuan Li, Ravi Janardan

Publication date: 18 August 2020

Abstract: Given a dataset $S$ of points in $mathbb{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 $ScapX$ 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.

Full work available at URL: https://arxiv.org/abs/1712.09749

zbMATH Keywords

average-case analysisrange searchcandidate pairsclosest-pair

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Point Location in a Monotone Subdivision
• Data structures for range-aggregate extent queries
• On the Power of the Semi-Separated Pair Decomposition
• New Bounds for Range Closest-Pair Problems

Cited In (7)

• Closest-pair queries and minimum-weight queries are equivalent for squares
• Closest-pair queries in fat rectangles
• New measures of proximity for the assignment algorithms in the MDVRPTW
• New bounds for range closest-pair problems
• New Bounds for Range Closest-Pair Problems
• Approximate range closest-pair queries
• Range closest-pair search in higher dimensions

This page was built for publication: New Bounds for Range Closest-Pair Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116533)