Closest-Pair Queries and Minimum-Weight Queries are Equivalent for Squares

Let $S$ be a set of $n$ weighted points in the plane and let $R$ be a query range in the plane. In the range closest pair problem, we want to report the closest pair in the set $R \cap S$. In the range minimum weight problem, we want to report the minimum weight of any point in the set $R \cap S$. We show that these two query problems are equivalent for query ranges that are squares, for data structures having $\Omega(\log n)$ query times. As a result, we obtain new data structures for range closest pair queries with squares.

• Publication year

  2020

• Venue

  Canadian Conference on Computational Geometry

• Publication date

  2020-10-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/J.COMGEO.2021.101810arXiv 2010.06463
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Range closest-pair search in higher dimensions

  2019cited by this paper
• Approximate Range Closest-Pair Search

  2018cited by this paper
• Closest-Pair Queries in Fat Rectangles

  2018influential reference
• New Bounds for Range Closest-Pair Problems

  2017cited by this paper
• On the power of the semi-separated pair decomposition

  2009cited by this paper
• Data structures for range-aggregate extent queries

  2008cited by this paper
• Range-Aggregate Proximity Queries

  2007cited by this paper
• Range-Aggregate Query Problems Involving Geometric Aggregation Operations

  2005cited by this paper
• On Spatial-Range Closest-Pair Query

  2003cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching

  1988cited by this paper
• Optimal Search in Planar Subdivisions

  1983cited by this paper
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

  1977cited by this paper

• No citing papers are available for this paper.