New bounds for range closest-pair problems

Jie Xue; Yuan Li; Saladi Rahul; Ravi Janardan

doi:10.4230/LIPIcs.SoCG.2018.73

New bounds for range closest-pair problems

Jie Xue
, Yuan Li
, Saladi Rahul
, Ravi Janardan

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

10 Scopus citations

Abstract

Given a dataset S of points in R², 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 S ∩ X 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.

Original language	English (US)
Title of host publication	34th International Symposium on Computational Geometry, SoCG 2018
Editors	Csaba D. Toth, Bettina Speckmann
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	731-7314
Number of pages	6584
ISBN (Electronic)	9783959770668
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2018.73
State	Published - Jun 1 2018
Event	34th International Symposium on Computational Geometry, SoCG 2018 - Budapest, Hungary Duration: Jun 11 2018 → Jun 14 2018

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	99
ISSN (Print)	1868-8969

Other

Other	34th International Symposium on Computational Geometry, SoCG 2018
Country/Territory	Hungary
City	Budapest
Period	6/11/18 → 6/14/18

Bibliographical note

Publisher Copyright:
© Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

Keywords

Average-case analysis
Candidate pairs
Closest-pair
Range search

Publisher link

10.4230/LIPIcs.SoCG.2018.73

Find It

Find It at U of M Libraries

Cite this

Xue, J., Li, Y., Rahul, S., & Janardan, R. (2018). New bounds for range closest-pair problems. In C. D. Toth, & B. Speckmann (Eds.), 34th International Symposium on Computational Geometry, SoCG 2018 (pp. 731-7314). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 99). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2018.73

New bounds for range closest-pair problems. / Xue, Jie; Li, Yuan; Rahul, Saladi et al.
34th International Symposium on Computational Geometry, SoCG 2018. ed. / Csaba D. Toth; Bettina Speckmann. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. p. 731-7314 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 99).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Xue, J, Li, Y, Rahul, S & Janardan, R 2018, New bounds for range closest-pair problems. in CD Toth & B Speckmann (eds), 34th International Symposium on Computational Geometry, SoCG 2018. Leibniz International Proceedings in Informatics, LIPIcs, vol. 99, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 731-7314, 34th International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, 6/11/18. https://doi.org/10.4230/LIPIcs.SoCG.2018.73

@inproceedings{b9991fbbcff64bdb8e003723b7f74d33,

title = "New bounds for range closest-pair problems",

abstract = "Given a dataset S of points in R2, 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 S ∩ X 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.",

keywords = "Average-case analysis, Candidate pairs, Closest-pair, Range search",

author = "Jie Xue and Yuan Li and Saladi Rahul and Ravi Janardan",

note = "Publisher Copyright: {\textcopyright} Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).; 34th International Symposium on Computational Geometry, SoCG 2018 ; Conference date: 11-06-2018 Through 14-06-2018",

year = "2018",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2018.73",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "731--7314",

editor = "Toth, \{Csaba D.\} and Bettina Speckmann",

booktitle = "34th International Symposium on Computational Geometry, SoCG 2018",

}

TY - GEN

T1 - New bounds for range closest-pair problems

AU - Xue, Jie

AU - Li, Yuan

AU - Rahul, Saladi

AU - Janardan, Ravi

N1 - Publisher Copyright: © Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan; licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

PY - 2018/6/1

Y1 - 2018/6/1

N2 - Given a dataset S of points in R2, 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 S ∩ X 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.

AB - Given a dataset S of points in R2, 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 S ∩ X 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.

KW - Average-case analysis

KW - Candidate pairs

KW - Closest-pair

KW - Range search

UR - https://www.scopus.com/pages/publications/85048974993

UR - https://www.scopus.com/pages/publications/85048974993#tab=citedBy

U2 - 10.4230/LIPIcs.SoCG.2018.73

DO - 10.4230/LIPIcs.SoCG.2018.73

M3 - Conference contribution

AN - SCOPUS:85048974993

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 731

EP - 7314

BT - 34th International Symposium on Computational Geometry, SoCG 2018

A2 - Toth, Csaba D.

A2 - Speckmann, Bettina

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 34th International Symposium on Computational Geometry, SoCG 2018

Y2 - 11 June 2018 through 14 June 2018

ER -

New bounds for range closest-pair problems

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this