A Simple Yet Fast Algorithm for the Closest-Pair Problem Using Sorted Projections on Multi-Dimensions

Basit Öğe Kaydı
dc.contributor.authorDalkilic, Mehmet E.
dc.contributor.authorErgun, Serkan
dc.contributor.editorGelenbe, E
dc.contributor.editorLent, R
dc.date.accessioned2019-10-27T21:42:18Z
dc.date.available2019-10-27T21:42:18Z
dc.date.issued2013
dc.departmentEge Üniversitesien_US
dc.description28th International Symposium on Computer and Information Sciences (ISCIS) -- OCT 28-29, 2013 -- Inst Henri Poincare, Paris, FRANCEen_US
dc.description.abstractWe present a simple greedy algorithm, QuickCP, for finding the closest-pair of points on a plane. It is based on the observation that if two points are close to each other, then it is very likely that their sorted projections to x-axis and/or to y-axis will reflect that closeness. Therefore we order our search starting from the pairs with closest x-projections (and closest y-projections) to find the closest pair quickly and make a fast exit. Empirical data up to 2(26) (over 60 million points) indicates that this approach quickly detects the closest pair and it is, on average 70% faster than the classical divide-and-conquer algorithm registering, to the best of our knowledge, the fastest recorded solution times in the literature for the planar closest-pair problem. A second contribution of our work is that QuickCP can be used as part of the divide-and-conquer algorithms to handle small sub-problems. Measurements on data up to 2(26) points show that this co-operation speeds up the basic divide-and-conquer algorithm on average 50%.en_US
dc.identifier.doi10.1007/978-3-319-01604-7_3
dc.identifier.endpage34en_US
dc.identifier.isbn978-3-319-01604-7; 978-3-319-01603-0
dc.identifier.issn1876-1100
dc.identifier.issn1876-1100en_US
dc.identifier.scopusqualityQ4en_US
dc.identifier.startpage23en_US
dc.identifier.urihttps://doi.org/10.1007/978-3-319-01604-7_3
dc.identifier.urihttps://hdl.handle.net/11454/46865
dc.identifier.volume264en_US
dc.identifier.wosWOS:000333692000003en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.language.isoenen_US
dc.publisherSpringeren_US
dc.relation.ispartofInformation Sciences and Systems 2013en_US
dc.relation.ispartofseriesLecture Notes in Electrical Engineering
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.titleA Simple Yet Fast Algorithm for the Closest-Pair Problem Using Sorted Projections on Multi-Dimensionsen_US
dc.typeConference Objecten_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu