Colored range closest-pair problem under general distance functions
Author: 
Jie XueAuthors Info & Claims
Pages 373 - 390
Abstract
The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range X is specified, the closest pair of points contained in X can be reported efficiently. A natural generalization of the RCP problem is the colored range closest-pair (CRCP) problem in which the given data points are colored and the goal is to find the closest bichromatic pair contained in the query range. All the previous work on the RCP problem was restricted to the uncolored version and the Euclidean distance function. In this paper, we make the first progress on the CRCP problem. We investigate the problem under a general distance function induced by a monotone norm; in particular, this covers all the Lp-metrics for p ≥ 1 and the L∞-metric. We design efficient (1+ε)-approximate CRCP data structures for orthogonal queries in R2, where ε > 0 is a pre-specified parameter. The highlights are two data structures for answering rectangle queries, one of which uses O(ε−1 n log4 n) space and O(log4 n + ε−1 log3 n + ε−2 log n) query time while the other uses O(ε−1 n log3 n) space and O(log5 n + ε−1 log4 n + ε−2 log2 n) query time, where n is the size of the input dataset. In addition, we also apply our techniques to the CRCP problem in higher dimensions, obtaining efficient data structures for slab, 2-box, and 3D dominance queries. Before this paper, almost all the existing results for the RCP problem were achieved in R2.
References
[1]
M. A. Abam, P. Carmi, M. Farshi, and M. Smid. On the power of the semi-separated pair decomposition. In Workshop on Algorithms and Data Structures, pages 1--12. Springer, 2009.
[2]
Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry, 6(3):407--422, 1991.
[3]
Pankaj K Agarwal, Jeff Erickson, et al. Geometric range searching and its relatives. Contemporary Mathematics, 223:1--56, 1999.
[4]
Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Geometric approximation via core-sets. Combinatorial and computational geometry, 52:1--30, 2005.
[5]
Sunil Arya and David M Mount. Approximate range searching. Computational Geometry, 17(3--4):135--152, 2000.
[6]
Bernard Chazelle, Ding Liu, and Avner Magen. Approximate range searching in higher dimension. Computational Geometry, 39(1):24--29, 2008.
[7]
M. de Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry. Springer Verlag, 2nd edition, 2000.
[8]
David Eppstein. Dynamic euclidean minimum spanning trees and extrema of binary functions. Discrete & Computational Geometry, 13(1):111--122, 1995.
[9]
Gereon Frahling and Christian Sohler. Coresets in dynamic geometric data streams. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 209--217. ACM, 2005.
[10]
Prosenjit Gupta. Range-aggregate query problems involving geometric aggregation operations. Nordic journal of Computing, 13(4):294--308, 2006.
[11]
Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, and Michiel Smid. Data structures for rangeaggregate extent queries. Computational Geometry: Theory and Applications, 2(47):329--347, 2014.
[12]
Sariel Har-Peled. Coresets for discrete integration and clustering. In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 33--44. Springer, 2006.
[13]
Sariel Har-Peled and Soham Mazumdar. On core-sets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291--300. ACM, 2004.
[14]
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.
[15]
R. Sharathkumar and P. Gupta. Range-aggregate proximity queries. Technical Report IIIT/TR/2007/80. IIIT Hyderabad, Telangana, 500032, 2007.
[16]
Michiel Smid. Closest point problems in computational geometry. Citeseer, 1995.
[17]
Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New bounds for range closest-pair problems. Proceedings of the 34th International Symposium on Computational Geometry, 2018.
- Colored range closest-pair problem under general distance functions
Recommendations
An efficient randomized algorithm for the closest pair problem on colored point sets
We present a simple randomized algorithm for finding the Closest Foreign Pair, in a set of n points in D-dimensional space, where D ≥ 2 is a fixed constant and the distances are measured in the L1 and the L∞ metric. The algorithm runs in O(nlogD-1 n/log ...
A Reliable Randomized Algorithm for the Closest-Pair Problem
The following two computational problems are studied:Duplicate grouping:Assume thatnitems are given, each of which is labeled by an integer key from the set {0, ,U 1}. Store the items in an array of sizensuch that items with the same key occupy a ...
Closest-pair queries in fat rectangles
AbstractIn the range closest pair problem, we want to construct a data structure storing a set S of n points in the plane, such that for any axes-parallel query rectangle R, the closest pair in the set R ∩ S can be reported. The currently best ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIAM Activity Group on Discrete Mathematics
In-Cooperation
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 06 January 2019
Check for updates
Qualifiers
- Research-article
Conference
SODA '19
Sponsor:
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 52Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)2
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in