{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:40:42Z","timestamp":1737006042479,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425601"},{"type":"electronic","value":"9783540448082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44808-x_8","type":"book-chapter","created":{"date-parts":[[2007,5,4]],"date-time":"2007-05-04T00:32:08Z","timestamp":1178238728000},"page":"105-116","source":"Crossref","is-referenced-by-count":1,"title":["PVD: A Stable Implementation for Computing Voronoi Diagrams of Polygonal Pockets"],"prefix":"10.1007","author":[{"given":"Saurabh","family":"Sethia","sequence":"first","affiliation":[]},{"given":"Martin","family":"Held","sequence":"additional","affiliation":[]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,11]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"T. Auer and M. Held. Heuristics for the generation of random polygons. In Proc. 8th Canad. Conf. Comput. Geom., pages 38\u201343, 1996.","DOI":"10.1515\/9780773591134-009"},{"key":"8_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BFb0049411","volume-title":"Proc. 2nd Annu. European Sympos. Algorithms","author":"C. Burnikel","year":"1994","unstructured":"C. Burnikel, K. Mehlhorn, and S. Schirra. How to compute the Voronoi diagram of line segments: Theoretical and experimental results. In Proc. 2nd Annu. European Sympos. Algorithms, vol. 855 of LNCS, pages 227\u2013239. Springer-Verlag, 1994."},{"key":"8_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/BFb0015444","volume-title":"Proc. 6th Annu. Internat. Sympos. Algorithms Comput.","author":"F. Chin","year":"1995","unstructured":"F. Chin, J. Snoeyink, and C.-A. Wang. Finding the medial axis of a simple polygon in linear time. In Proc. 6th Annu. Internat. Sympos. Algorithms Comput., vol. 1004 of LNCS, pages 382\u2013391. Springer-Verlag, 1995."},{"key":"8_CR4","unstructured":"R. L. Drysdale, III. Generalized Voronoi Diagrams and Geometric Searching. Ph.D. thesis, Dept. Se, Stanford Univ., CA, USA, 1979. Report STAN-CS-79-705."},{"key":"8_CR5","unstructured":"M. Held. http:\/\/www.cosy.sbg.ac.at\/~held\/ project\/vroni\/vroni.html"},{"key":"8_CR6","unstructured":"M. Held. VRONI: An Engineering Approach to the Reliable and Efficient Computation f Voronoi Diagrams of Points and Line Segments. To appear in Computational Geometry: Theory and Applications."},{"key":"8_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-54103-9","volume-title":"On the Computational Geometry of Pocket Machining","author":"M. Held","year":"1991","unstructured":"M. Held. On the Computational Geometry of Pocket Machining, vol. 500 of LNCS Springer-Verlag, June 1991."},{"issue":"4","key":"8_CR8","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0010-4485(97)00071-7","volume":"30","author":"M. Held","year":"1998","unstructured":"M. Held. Voronoi diagrams and offset curves of curvilinear polygons. Comput. Aided Design, 30(4):287\u2013300, Apr. 1998.","journal-title":"Comput. Aided Design"},{"key":"8_CR9","unstructured":"M. Held. Computing Voronoi diagrams of line segments reliably and effciently. In Proc. 12th Canad. Conf. on Comput. Geom., pages 115\u2013118, Fredericton, NB, Canada, 2000."},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"K. E. H. III, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proc. SIGGRAPH\u201999, In Comput. Graph., pages 277\u2013285. ACM SIGGRAPH, Addison-Wesley, 1999.","DOI":"10.1145\/311535.311567"},{"key":"8_CR11","first-page":"107","volume-title":"Proc. 8th Canad. Conf. Comput. Geom.","author":"T. Imai","year":"1996","unstructured":"T. Imai. A topology oriented algorithm for the Voronoi diagram of polygons. In Proc. 8th Canad. Conf. Comput. Geom., pages 107\u2013112. Carleton University Press, Ottawa, Canada, 1996."},{"key":"8_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"R. Klein","year":"1989","unstructured":"R. Klein. Concrete and Abstract Voronoi Diagrams, vol. 400 of LNCS Springer-Verlag, 1989."},{"issue":"4","key":"8_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TPAMI.1982.4767267","volume":"PAMI-4","author":"D. T. Lee","year":"1982","unstructured":"D. T. Lee. Medial axis transformation of a planar shape. IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4(4):363\u2013369, 1982.","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1137\/0210006","volume":"10","author":"D. T. Lee","year":"1981","unstructured":"D. T. Lee and R. L. Drysdale, III. Generalization of Voronoi diagrams in the plane. SIAM J. Comput., 10:73\u201387, 1981.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539796305365","volume":"28","author":"G. Liotta","year":"1998","unstructured":"G. Liotta, F. P. Preparata, and R. Tamassia. Robust proximity queries: An illustration of degree-driven algorithm design. SIAM J. Comput., 28(3):864\u2013889, 1998.","journal-title":"SIAM J. Comput."},{"key":"8_CR16","volume-title":"Report A 04\/89","author":"K. Mehlhorn","year":"1989","unstructured":"K. Mehlhorn and S. N\u00e4her. LEDA, a library of efficient data types and algorithms. Report A 04\/89, Univ. Saarlandes, Saarbr\u00fccken, Germany, 1989."},{"key":"8_CR17","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A. Okabe","year":"1992","unstructured":"A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK, 1992."},{"issue":"3","key":"8_CR18","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0010-4485(78)90141-0","volume":"10","author":"H. Persson","year":"1978","unstructured":"H. Persson. NC machining of arbitrarily shaped pockets. Comput. Aided Design, 10(3):169\u2013174, May 1978.","journal-title":"Comput. Aided Design"},{"key":"8_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/3-540-08353-7_166","volume-title":"Proc. 6th Internat. Sympos. Math. Found. Comput. Sci.","author":"F. P. Preparata","year":"1977","unstructured":"F. P. Preparata. The medial axis of a simple polygon. In Proc. 6th Internat. Sympos. Math. Found. Comput. Sci., vol. 53 of LNCS, pages 443\u2013450. Springer-Verlag, 1977."},{"key":"8_CR20","unstructured":"S. Sethia. PhD thesis, SUNY at Stony Brook, NY 11794, USA., May 2001."},{"issue":"9","key":"8_CR21","doi-asserted-by":"crossref","first-page":"1471","DOI":"10.1109\/5.163412","volume":"80","author":"K. Sugihara","year":"1992","unstructured":"K. Sugihara and M. Iri. Construction of the Voronoi diagram for \u2018one million\u2019 generators in single-precision arithmetic. Proc. IEEE, 80(9):1471\u20131484, Sept. 1992.","journal-title":"Proc. IEEE"},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1515\/crll.1908.134.198","volume":"134","author":"G. M. Voronoi","year":"1908","unstructured":"G. M. Voronoi. Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. deuxi\u00e8me M\u00e9moire: Recherches sur les parall\u00e9llo\u00e8dres primitifs. J. Reine Angew. Math., 134:198\u2013287, 1908.","journal-title":"J. Reine Angew. Math."},{"key":"8_CR23","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 Engineering and Experimentation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44808-X_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T01:54:01Z","timestamp":1736992441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44808-X_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425601","9783540448082"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-44808-x_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}