{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T17:37:33Z","timestamp":1725817053873},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319156118"},{"type":"electronic","value":"9783319156125"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15612-5_12","type":"book-chapter","created":{"date-parts":[[2015,2,22]],"date-time":"2015-02-22T23:05:18Z","timestamp":1424646318000},"page":"125-136","source":"Crossref","is-referenced-by-count":1,"title":["An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments"],"prefix":"10.1007","author":[{"given":"Sang Won","family":"Bae","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00454-005-1192-0","volume":"34","author":"H. Alt","year":"2005","unstructured":"Alt, H., Cheong, O., Vigneron, A.: The Voronoi diagram of curved objects. Discrete Comput. Geom.\u00a034(3), 439\u2013453 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR2","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry. Elsevier (2000)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Chang, H., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: Proc. 26th ACM-SIAM Sympos. Discrete Algo (SODA 2015) (2015)","DOI":"10.1137\/1.9781611973730.110"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom.\u00a06, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/147508.147511","volume":"39","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM\u00a039, 1\u201354 (1992)","journal-title":"J. ACM"},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/PL00009429","volume":"21","author":"F. Chin","year":"1999","unstructured":"Chin, F., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom.\u00a021(3), 405\u2013420 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S.J. Fortune","year":"1987","unstructured":"Fortune, S.J.: A sweepline algorithm for Voronoi diagrams. Algorithmica\u00a02, 153\u2013174 (1987)","journal-title":"Algorithmica"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","volume-title":"On the Computational Geometry of Pocket Machining","year":"1991","unstructured":"Held, M. (ed.): On the Computational Geometry of Pocket Machining. LNCS, vol.\u00a0500. Springer, Heidelberg (1991)"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.: Optimal search in planar subdivisions. SIAM J. Comput.\u00a012(1), 28\u201335 (1983)","journal-title":"SIAM J. Comput."},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeleton. In: Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., pp. 18\u201327 (1979)","DOI":"10.1109\/SFCS.1979.15"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"R. Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. LNCS, vol.\u00a0400. Springer, Heidelberg (1989)"},{"issue":"3","key":"12_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R. Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract Voronoi diagrams. Comput. Geom.: Theory Appl.\u00a03(3), 157\u2013184 (1993)","journal-title":"Comput. Geom.: Theory Appl."},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TPAMI.1982.4767267","volume":"4","author":"D.T. Lee","year":"1982","unstructured":"Lee, D.T.: Medial axis transformation of a planar shape. IEEE Trans. Pattern Anal. Mach. Intell. PAMI\u00a04(4), 363\u2013369 (1982)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. PAMI"},{"key":"12_CR14","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"2000","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. John Wiley and Sons, New York (2000)","edition":"2"},{"key":"12_CR15","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1147\/rd.313.0361","volume":"31","author":"V. Srinivasan","year":"1987","unstructured":"Srinivasan, V., Nackman, L.R.: Voronoi diagram for multiply-connected polygonal domains I: Algorithm. IBM J. Research Development\u00a031(3), 361\u2013372 (1987)","journal-title":"IBM J. Research Development"},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"C.K. Yap","year":"1987","unstructured":"Yap, C.K.: An O(n logn) algorithm for the Voronoi diagram of a set of simple curve segments. Discrete Comput. Geom.\u00a02(1), 365\u2013393 (1987)","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15612-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T06:26:33Z","timestamp":1559111193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-15612-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319156118","9783319156125"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15612-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}