New bounds for range closest-pair problems

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

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

Publication date 18 August 2020

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)

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.

Recommendations

• Approximate range closest-pair queries
• Colored range closest-pair problem under general distance functions
• New Techniques for Exact and Approximate Dynamic Closest-Point Problems

Cites work

• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Data structures for range-aggregate extent queries
• New bounds for range closest-pair problems
• On the Power of the Semi-Separated Pair Decomposition
• Optimal Point Location in a Monotone Subdivision
• Range-aggregate query problems involving geometric aggregation operations

Cited in

(9)

• Closest-pair queries in fat rectangles
• New bounds for range closest-pair problems
• A new plane-sweep algorithm for the \(K\)-closest-pairs query
• Searching for the closest-pair in a query translate
• Closest-pair queries and minimum-weight queries are equivalent for squares
• Approximate range closest-pair queries
• New bounds for range closest-pair problems
• New measures of proximity for the assignment algorithms in the MDVRPTW
• Colored range closest-pair problem under general distance functions

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)