{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:46Z","timestamp":1787337466505,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D &gt; 1. The data structure can be modified to run in O(log\n                    <jats:sup>2<\/jats:sup>\n                    n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D &gt; 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794277718","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1036-1072","source":"Crossref","is-referenced-by-count":6,"title":["Randomized Data Structures for the Dynamic Closest-Pair Problem"],"prefix":"10.1137","volume":"27","author":[{"given":"Mordecai","family":"Golin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Schwarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010Or,\n                      Lower bounds for algebraic computation trees\n                      , in Proc. 15th Ann. ACM Sympos. Theory Comput., 1983, pp. 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Jon Bentley, Michael Shamos, Divide\u2010and\u2010conquer in multidimensional space, Assoc. Comput. Mach., New York, 1976, 220\u201323055:13869","DOI":"10.1145\/800113.803652"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. N. Bespamyatnikh,\n                      An optimal algorithm for closest pair maintenance\n                      , in Proc. 11th Ann. ACM Sympos. Comput. Geom., 1995, pp. 152\u2013161.","DOI":"10.1145\/220279.220296"},{"key":"R4","unstructured":"Paul Callahan, S. Kosaraju, Algorithms for dynamic closest pair and n\u2010body potential fields, ACM, New York, 1995, 263\u201327296e:68125"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"R6","volume-title":"Introduction to algorithms","author":"Manber Udi","year":"1989"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000147"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01890115"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1048"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"R11","first-page":"3","volume":"2","author":"Golin Mordecai","year":"1995","journal-title":"Nordic J. Comput."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1049"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259458"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Ragahavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, London, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"R16","unstructured":"Michael Rabin, Probabilistic algorithms, Academic Press, New York, 1976, 21\u20133957:4603"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000044"},{"key":"R18","unstructured":"C. Schwarz,\n                      Data Structures and Algorithms for the Dynamic Closest Pair Problem\n                      , Ph.D. thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1993."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900061"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Michael Shamos, Dan Hoey, Closest\u2010point problems, IEEE Computer Society, Long Beach, Calif., 1975, 151\u201316254:14441","DOI":"10.1109\/SFCS.1975.8"},{"key":"R21","first-page":"33","volume":"2","author":"Smid M.","year":"1991","journal-title":"Algorithms Rev."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187852"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377181"},{"key":"R24","unstructured":"K. J. Supowit,\n                      New techniques for some dynamic closest\u2010point and farthest\u2010point problems\n                      , in Proc. 1st ACM\u2010SIAM Sympos. Discrete Algorithms, 1990, pp. 84\u201390."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794277718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:05Z","timestamp":1787335925000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794277718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794277718"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794277718","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}