Abstract
We consider a range-search variant of the closest-pair problem. Let Γ be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Γ, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Γ is a polygon (possibly with holes) and when Γ is a general convex body whose boundary is smooth. When Γ is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Γ is a general convex body with a smooth boundary, we give a near-optimal data structure using O(nlog n) space and O(log2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.
| Original language | English (US) |
|---|---|
| Title of host publication | 35th International Symposium on Computational Geometry, SoCG 2019 |
| Editors | Gill Barequet, Yusu Wang |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959771047 |
| DOIs | |
| State | Published - Jun 1 2019 |
| Event | 35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States Duration: Jun 18 2019 → Jun 21 2019 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 129 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 35th International Symposium on Computational Geometry, SoCG 2019 |
|---|---|
| Country/Territory | United States |
| City | Portland |
| Period | 6/18/19 → 6/21/19 |
Bibliographical note
Funding Information:Funding The research of Jie Xue is supported, in part, by a Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota.
Publisher Copyright:
© Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan.
Keywords
- And phrases Closest pair
- Geometric data structures
- Range search
- Translation query