{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:53Z","timestamp":1787340653327,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>Efficient algorithms for detecting intersections and computing closest neighbors in a set of circular discs, are presented and analyzed. They adapt known techniques for solving these problems for sets of points or of line segments. The main portion of the paper contains the construction of a generalized Voronoi diagram for a set of n (possibly intersecting) circular discs in time $O(n\\log ^2 n)$, and its applications.<\/jats:p>","DOI":"10.1137\/0214034","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"448-468","source":"Crossref","is-referenced-by-count":71,"title":["Intersection and Closest-Pair Problems for a Set of Planar Discs"],"prefix":"10.1137","volume":"14","author":[{"given":"Micha","family":"Sharir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RBO","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"RD","unstructured":"R. L. Drysdale, III, Ph.D. Thesis,  Generalized Voronoi diagrams and geometric searching, Dept. Computer Science, Stanford Univ., Stanford, CA,  1979, STAN-CS-79-705"},{"key":"RDL","first-page":"833","volume-title":"Sixteenth Annual Allerton Conference on Communication, Control, and Computing","author":"Drysdale, III R. L.","year":"1978"},{"key":"RHSS","doi-asserted-by":"publisher","DOI":"10.1177\/027836498300200405"},{"key":"RKI","doi-asserted-by":"crossref","unstructured":"D. Kirkpatrick,  Efficient computation of continuous skeletons,  Proc. 20th Symposium on Foundations of Computer Science,  1979,  18\u201327","DOI":"10.1109\/SFCS.1979.15"},{"key":"RKI2","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"RLD","doi-asserted-by":"publisher","DOI":"10.1137\/0210006"},{"key":"RNP","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"RPR","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"RSH","unstructured":"M. I. Shamos, Masters Thesis,  Computational geometry, Ph.D. Dissertation, Yale Univ., New Haven, CT,  1975"},{"key":"RSS","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160360305"},{"key":"RSP","unstructured":"P. Spirakis,  Very fast algorithms for the area of the union of many circles, Tech. Rept., Computer Science Dept., Courant Institute, New York Univ., New York,  1983, December"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:58Z","timestamp":1787337778000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214034"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214034"],"URL":"https:\/\/doi.org\/10.1137\/0214034","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}