{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:32:31Z","timestamp":1742913151493,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054355","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"59-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An optimal algorithm for computing visible nearest foreign neighbors among colored line segments"],"prefix":"10.1007","author":[{"given":"Thorsten","family":"Graf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kamakoti","family":"Veezhinathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"issue":"1","key":"6_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(92)90133-G","volume":"42","author":"A. Aggarwal","year":"1992","unstructured":"A. Aggarwal, H. Edelsbrunner, P. Raghavan, and P. Tiwari. Optimal time bounds for some proximity problems in the plane. Inform. Process. Lett, 42(1):55\u201360, 1992.","journal-title":"Inform. Process. Lett"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"F. Bartling and K. Hinrichs. A plane-sweep algorithm for finding a closest pair among convex planar objects. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lecture Notes in Computer Science, pages 221\u2013232. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55210-3_186"},{"key":"6_CR3","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"C-28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643\u2013647, 1979.","journal-title":"IEEE Trans. Comput."},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"C. Brunikel, K. Mehlhorn, and S. Schirra. How to compute the voronoi diagram of Une segments: Theoretical and experimental results. In Proc. European Symposium on Algorithms, volume 855 of Lecture Notes in Computer Science, pages 227\u2013239. Springer-Verlag, 1994.","DOI":"10.1007\/BFb0049411"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"S. Fortune. Numerical stability of algorithms for 2-d Delaunay triangulations and Voronoi diagrams. In Proc. 8th Annu. ACM Sympos. Comput. Geom., pages 83\u201392, 1992.","DOI":"10.1145\/142675.142695"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"S. Fortune and V. Milenkovic. Numerical stability of algorithms for line arrangements. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 334\u2013341, 1991.","DOI":"10.1145\/109648.109685"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. J. Fortune","year":"1987","unstructured":"S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153\u2013174, 1987.","journal-title":"Algorithmica"},{"key":"6_CR8","unstructured":"T. Graf and K. Hinrichs. Algorithms for proximity problems on colored point sets. In Proc. 5th Canad. Conf. Comput. Geom., pages 420\u2013425, Waterloo, Canada, 1993."},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"T. Graf and K. Hinrichs. A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes in Computer Science, pages 349\u2013360. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-57155-8_261"},{"key":"6_CR10","unstructured":"T. Graf and K. Hinrichs. Distribution algorithms for the all-nearest-foreignneighbors problem in arbitrary Lt metrics. In Proc. 6th Canad. Conf. Comput. Geom., pages 69\u201374, 1994."},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12:28\u201335, 1983.","journal-title":"SIAM J. Comput."},{"key":"6_CR12","unstructured":"I. Masser and M. Blakemore, editors. Handling geographical information: methodology and potential applications. Long Scientific &: Technical, 1991."},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02716580","volume":"15","author":"M. McAllister","year":"1996","unstructured":"M. McAllister, D. Kirkpatrick, and J. Snoeyink. A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discrete Comput. Geom., 15:73\u2013105, 1996.","journal-title":"Discrete Comput. Geom."},{"key":"6_CR14","volume-title":"Report MPI-I-94-160","author":"K. Mehlhorn","year":"1994","unstructured":"K. Mehlhorn and S. N\u00c4her. Implementation of a sweep line algorithm for the straight line segment intersection problem. Report MPI-I-94-160, Max-Planck-Institut Inform., Saarbr\u00fccken, Germany, 1994."},{"key":"6_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985."},{"key":"6_CR16","volume-title":"Computational Aspects of VLSI Design","author":"J. D. Ullman","year":"1984","unstructured":"J. D. Ullman. Computational Aspects of VLSI Design. Computer Science Press Inc., Maryland, 1984."},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"C. K. Yap","year":"1987","unstructured":"C. K. Yap. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete Comput. Geom., 2:365\u2013393, 1987.","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T20:05:07Z","timestamp":1674072307000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0054355","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}