2020/10/13 by Abrar Kazi, Kazi, Abrar, Michiel Smid +1
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.2010.06463
arxiv created 2020/10/13 · openalex publication_date 2020/10/13 · arxiv updated 2020/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ∩ S. In the range minimum weight problem, we want to report the minimum weight of any point in the set R ∩ S. We show that these two query problems are equivalent for query ranges that are squares, for data structures having Ω(log n) query times. As a result, we obtain new data structures for range closest pair queries with squares.