Dynamic closest pairs - A probabilistic approach

Mordecai J. Golin

doi:10.1007/3-540-55706-7_31

Dynamic closest pairs - A probabilistic approach

Mordecai J. Golin^*

^*Corresponding author for this work

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

Abstract

The dynamic closest pair problem is to find the closest pair among a set of points that is continuously being changed by insertions and deletions. In this paper we present a simple, robust, easily coded heuristic for solving the planar closest pair problem. We prove that this heuristic uses only O(log n) expected time to perform an insertion or deletion when the input points are chosen fxom a very wide class of distributions in the plane.

Original language	English
Title of host publication	Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
Editors	Otto Nurmi, Esko Ukkonen
Publisher	Springer Verlag
Pages	340-351
Number of pages	12
ISBN (Print)	9783540557067
DOIs	https://doi.org/10.1007/3-540-55706-7_31
Publication status	Published - 1992
Externally published	Yes
Event	3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 - Helsinki, Finland Duration: 8 Jul 1992 → 10 Jul 1992

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	621 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992
Country/Territory	Finland
City	Helsinki
Period	8/07/92 → 10/07/92

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

Access to Document

10.1007/3-540-55706-7_31

Cite this

Golin, M. J. (1992). Dynamic closest pairs - A probabilistic approach. In O. Nurmi, & E. Ukkonen (Eds.), Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 340-351). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 621 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-55706-7_31

Golin, Mordecai J. / Dynamic closest pairs - A probabilistic approach. Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. editor / Otto Nurmi ; Esko Ukkonen. Springer Verlag, 1992. pp. 340-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2e6173d5f4c146b486628dc9395d8f16,

title = "Dynamic closest pairs - A probabilistic approach",

abstract = "The dynamic closest pair problem is to find the closest pair among a set of points that is continuously being changed by insertions and deletions. In this paper we present a simple, robust, easily coded heuristic for solving the planar closest pair problem. We prove that this heuristic uses only O(log n) expected time to perform an insertion or deletion when the input points are chosen fxom a very wide class of distributions in the plane.",

author = "Golin, \{Mordecai J.\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 ; Conference date: 08-07-1992 Through 10-07-1992",

year = "1992",

doi = "10.1007/3-540-55706-7\_31",

language = "English",

isbn = "9783540557067",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "340--351",

editor = "Otto Nurmi and Esko Ukkonen",

booktitle = "Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings",

}

Golin, MJ 1992, Dynamic closest pairs - A probabilistic approach. in O Nurmi & E Ukkonen (eds), Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 621 LNCS, Springer Verlag, pp. 340-351, 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992, Helsinki, Finland, 8/07/92. https://doi.org/10.1007/3-540-55706-7_31

Dynamic closest pairs - A probabilistic approach. / Golin, Mordecai J.
Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. ed. / Otto Nurmi; Esko Ukkonen. Springer Verlag, 1992. p. 340-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 621 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Dynamic closest pairs - A probabilistic approach

AU - Golin, Mordecai J.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - The dynamic closest pair problem is to find the closest pair among a set of points that is continuously being changed by insertions and deletions. In this paper we present a simple, robust, easily coded heuristic for solving the planar closest pair problem. We prove that this heuristic uses only O(log n) expected time to perform an insertion or deletion when the input points are chosen fxom a very wide class of distributions in the plane.

AB - The dynamic closest pair problem is to find the closest pair among a set of points that is continuously being changed by insertions and deletions. In this paper we present a simple, robust, easily coded heuristic for solving the planar closest pair problem. We prove that this heuristic uses only O(log n) expected time to perform an insertion or deletion when the input points are chosen fxom a very wide class of distributions in the plane.

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

U2 - 10.1007/3-540-55706-7_31

DO - 10.1007/3-540-55706-7_31

M3 - Conference Paper published in a book

AN - SCOPUS:85030571046

SN - 9783540557067

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 351

BT - Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Nurmi, Otto

A2 - Ukkonen, Esko

PB - Springer Verlag

T2 - 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

Y2 - 8 July 1992 through 10 July 1992

ER -

Golin MJ. Dynamic closest pairs - A probabilistic approach. In Nurmi O, Ukkonen E, editors, Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. Springer Verlag. 1992. p. 340-351. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-55706-7_31

Dynamic closest pairs - A probabilistic approach

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this