dc.contributor.author
Maheshwari, Anil
dc.contributor.author
Mulzer, Wolfgang
dc.contributor.author
Smid, Michiel
dc.date.accessioned
2021-05-10T07:46:57Z
dc.date.available
2021-05-10T07:46:57Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/30698
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-30437
dc.description.abstract
Consider a metric space (P, dist) with N points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in O(N log N) expected time, the closest-pair distance in P. To generate recursive calls, we use previous results of Har-Peled and Mendel, and Abam and Har-Peled for computing a sparse annulus that separates the points in a balanced way.
en
dc.format.extent
18 Seiten
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
computational geometry
en
dc.subject
doubling dimension
en
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
A simple randomized O(N log N)–time closest-pair algorithm in doubling metrics
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation.doi
10.20382/jocg.v11i1a20
dcterms.bibliographicCitation.journaltitle
Journal of Computational Geometry
dcterms.bibliographicCitation.number
1
dcterms.bibliographicCitation.pagestart
507
dcterms.bibliographicCitation.pageend
524
dcterms.bibliographicCitation.volume
11
dcterms.bibliographicCitation.url
https://doi.org/10.20382/jocg.v11i1a20
refubium.affiliation
Mathematik und Informatik
refubium.affiliation.other
Institut für Informatik / Theoretische Informatik
refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.eissn
1920-180X
refubium.resourceType.provider
WoS-Alert
