{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:23:56Z","timestamp":1774628636025,"version":"3.50.1"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p> Let S be a set of n points in D-dimensional space, where D is a constant, and let k be an integer between 1 and [Formula: see text]. A new and simpler proof is given of Salowe\u2019s theorem, i.e., a sequential algorithm is given that computes the k closest pairs in the set S in O(n log n+k) time, using O(n+k) space. The algorithm fits in the algebraic decision tree model and is, therefore, optimal. Salowe\u2019s algorithm seems difficult to parallelize. A parallel version of our algorithm is given for the CRCW-PRAM model. This version runs in O((log n)<jats:sup>2<\/jats:sup> log log n) expected parallel time and has an O(n log n log log n+k) time-processor product. Finally, actual running times are given of an implementation of our sequential algorithm. <\/jats:p>","DOI":"10.1142\/s0218195995000167","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T06:14:37Z","timestamp":1100067277000},"page":"273-288","source":"Crossref","is-referenced-by-count":17,"title":["SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE k CLOSEST PAIRS PROBLEM"],"prefix":"10.1142","volume":"05","author":[{"given":"HANS-PETER","family":"LENHOF","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik D-66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHIEL","family":"SMID","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik D-66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195995000167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:30:47Z","timestamp":1565123447000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195995000167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,9]]}},"alternative-id":["10.1142\/S0218195995000167"],"URL":"https:\/\/doi.org\/10.1142\/s0218195995000167","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}