Selecting distances in the plane

Pankaj K. Agarwal; Boris Aronov; Micha Sharir; Subhash Suri

doi:10.1145/98524.98597

Selecting distances in the plane

Pankaj K. Agarwal, Boris Aronov, Micha Sharir, Subhash Suri

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

Abstract

We describe a randomized algorithm for computing the k^th smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo. The expected running time of our algorithm is O(n^4/3 log^8/3 n). A deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). Both versions improve the previously best known upper bound of O(n^9/5 log^4/5 n) by Chazelle. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.

Original language	English (US)
Title of host publication	Proc Sixth Annu Symp Comput Geom
Publisher	Publ by ACM
Pages	321-331
Number of pages	11
ISBN (Print)	0897913620, 9780897913621
DOIs	https://doi.org/10.1145/98524.98597
State	Published - 1990
Event	Proceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA Duration: Jun 6 1990 → Jun 8 1990

Publication series

Name	Proc Sixth Annu Symp Comput Geom

Conference

Conference	Proceedings of the Sixth Annual Symposium on Computational Geometry
City	Berkeley, CA, USA
Period	6/6/90 → 6/8/90

ASJC Scopus subject areas

General Engineering

Access to Document

10.1145/98524.98597

Cite this

@inproceedings{91688a8e93dd4cb79ea1be2f4f73b72e,

title = "Selecting distances in the plane",

abstract = "We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo. The expected running time of our algorithm is O(n4/3 log8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.",

author = "Agarwal, {Pankaj K.} and Boris Aronov and Micha Sharir and Subhash Suri",

year = "1990",

doi = "10.1145/98524.98597",

language = "English (US)",

isbn = "0897913620",

series = "Proc Sixth Annu Symp Comput Geom",

publisher = "Publ by ACM",

pages = "321--331",

booktitle = "Proc Sixth Annu Symp Comput Geom",

note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",

}

TY - GEN

T1 - Selecting distances in the plane

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Sharir, Micha

AU - Suri, Subhash

PY - 1990

Y1 - 1990

N2 - We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo. The expected running time of our algorithm is O(n4/3 log8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.

AB - We describe a randomized algorithm for computing the kth smallest distance in a set of n points in the plane, based on the parametric search technique of Megiddo. The expected running time of our algorithm is O(n4/3 log8/3 n). A deterministic version of our procedure runs in time O(n3/2 log5/2 n). Both versions improve the previously best known upper bound of O(n9/5 log4/5 n) by Chazelle. A simple O(n log n) time algorithm for computing an approximation of the median distance is also presented.

UR - http://www.scopus.com/inward/record.url?scp=0025103141&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025103141&partnerID=8YFLogxK

U2 - 10.1145/98524.98597

DO - 10.1145/98524.98597

M3 - Conference contribution

AN - SCOPUS:0025103141

SN - 0897913620

SN - 9780897913621

T3 - Proc Sixth Annu Symp Comput Geom

SP - 321

EP - 331

BT - Proc Sixth Annu Symp Comput Geom

PB - Publ by ACM

T2 - Proceedings of the Sixth Annual Symposium on Computational Geometry

Y2 - 6 June 1990 through 8 June 1990

ER -

Selecting distances in the plane

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this