{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T11:10:37Z","timestamp":1776769837084,"version":"3.51.2"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NRF","award":["2015R1D1A1A01061361"],"award-info":[{"award-number":["2015R1D1A1A01061361"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            Voronoi diagrams are useful for spatial reasoning, and the robust and efficient construction of the ordinary Voronoi diagram of points is well known. However, its counterpart for circular disks in R\n            <jats:sup>2<\/jats:sup>\n            and spherical balls in R\n            <jats:sup>3<\/jats:sup>\n            remains a challenge. In this article, we propose a topology-oriented incremental algorithm which robustly and efficiently computes a Voronoi diagram by incrementing a new disk generator to an existing one. The key idea is to enforce the convexity of the Voronoi cell corresponding to the incrementing disk so that a simple variation of the algorithm for points proposed by Sugihara in 1992 can be applied. A benchmark using both random and degenerate disks shows that the proposed algorithm is superior to CGAL in both computational efficiency and algorithmic robustness.\n          <\/jats:p>","DOI":"10.1145\/2939366","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T12:14:20Z","timestamp":1471349660000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks"],"prefix":"10.1145","volume":"43","author":[{"given":"Mokwon","family":"Lee","sequence":"first","affiliation":[{"name":"Hanyang University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kokichi","family":"Sugihara","sequence":"additional","affiliation":[{"name":"Meiji University, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deok-Soo","family":"Kim","sequence":"additional","affiliation":[{"name":"Hanyang University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276896"},{"key":"e_1_2_1_3_1","volume-title":"Qualitative symbolic perturbation: A new geometry-based perturbation framework. INRIA","author":"Devillers Olivier","year":"2015","unstructured":"Olivier Devillers , Menelaos Karavelas , and Monique Teillaud . 2015. Qualitative symbolic perturbation: A new geometry-based perturbation framework. INRIA ( 2015 ), 34. Olivier Devillers, Menelaos Karavelas, and Monique Teillaud. 2015. Qualitative symbolic perturbation: A new geometry-based perturbation framework. INRIA (2015), 34."},{"key":"e_1_2_1_4_1","volume-title":"16th Annual Allerton Conference on Communications, Control and Computing","author":"Drysdale R. L.","year":"1978","unstructured":"R. L. Drysdale and D. T. Lee . 1978. Generalized Voronoi diagram in the plane . 16th Annual Allerton Conference on Communications, Control and Computing ( 1978 ), 833--842. R. L. Drysdale and D. T. Lee. 1978. Generalized Voronoi diagram in the plane. 16th Annual Allerton Conference on Communications, Control and Computing (1978), 833--842."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11%3C1167::AID-SPE337%3E3.0.CO;2-B"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161015"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231735"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(98)00039-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(03)00027-X"},{"key":"e_1_2_1_13_1","volume-title":"Goodman and Joseph ORourke","author":"Jacob","year":"1997","unstructured":"Jacob E. Goodman and Joseph ORourke . 1997 . Handbook of Discrete and Computational Geometry. CRC Press . Jacob E. Goodman and Joseph ORourke. 1997. Handbook of Discrete and Computational Geometry. CRC Press."},{"key":"e_1_2_1_14_1","unstructured":"Gaurav Gupta R. K. Ghosh and S. V. Rao. 2003. A routing algorithm for multi-hop mobile ad-hoc networks using weighted Delaunay triangulation. CIT (2003) 1--6.  Gaurav Gupta R. K. Ghosh and S. V. Rao. 2003. A routing algorithm for multi-hop mobile ad-hoc networks using weighted Delaunay triangulation. CIT (2003) 1--6."},{"key":"e_1_2_1_15_1","series-title":"Lecture Notes in Computer Science","volume-title":"On the Computational Geometry of Pocket Machining","author":"Held Martin","unstructured":"Martin Held . 1991. On the Computational Geometry of Pocket Machining . Lecture Notes in Computer Science , Vol. 500 . Springer-Verlag . Martin Held. 1991. On the Computational Geometry of Pocket Machining. Lecture Notes in Computer Science, Vol. 500. Springer-Verlag."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00003-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2008.08.004"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2005.11.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Menelaos Karavelas and Mariette Yvinec. 2002. Dynamic additively weighted Voronoi diagrams in 2d. In Algorithms-ESA2002. 586--598.   Menelaos Karavelas and Mariette Yvinec. 2002. Dynamic additively weighted Voronoi diagrams in 2d. In Algorithms-ESA2002. 586--598.","DOI":"10.1007\/3-540-45749-6_52"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.03.005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.06.002"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.06.004"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(95)99797-C"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(01)00050-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(01)00051-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.22956"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.7315\/JCDE.2014.008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/prot.24537"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkv360"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210006"},{"key":"e_1_2_1_32_1","volume-title":"Principles of CAD\/CAM\/CAE Systems","author":"Lee Kunwoo","unstructured":"Kunwoo Lee . 1999. Principles of CAD\/CAM\/CAE Systems . Addison-Wesley , Boston . Kunwoo Lee. 1999. Principles of CAD\/CAM\/CAE Systems. Addison-Wesley, Boston."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1204831"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2430342"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(91)90222-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01025983"},{"key":"e_1_2_1_37_1","volume-title":"Vehicular Technology Conference. 1--5.","author":"Mahboubi Hamid","unstructured":"Hamid Mahboubi and Amir G. Aghdam . 2013. An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges . In Vehicular Technology Conference. 1--5. Hamid Mahboubi and Amir G. Aghdam. 2013. An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges. In Vehicular Technology Conference. 1--5."},{"key":"e_1_2_1_38_1","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn Kurt","year":"1999","unstructured":"Kurt Mehlhorn and Stefan N\u00e4her . 1999 . LEDA: A Platform for Combinatorial and Geometric Computing . Cambridge University Press . Kurt Mehlhorn and Stefan N\u00e4her. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 5th International Symposium on Voronoi Diagrams in Science and Engineering. 22--28","author":"Nishida T.","unstructured":"T. Nishida and K. Sugihara . 2008. Precision necessary for d-dimensional sphere voronoi diagrams . In Proceedings of the 5th International Symposium on Voronoi Diagrams in Science and Engineering. 22--28 . T. Nishida and K. Sugihara. 2008. Precision necessary for d-dimensional sphere voronoi diagrams. In Proceedings of the 5th International Symposium on Voronoi Diagrams in Science and Engineering. 22--28."},{"key":"e_1_2_1_41_1","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"Okabe A.","year":"1999","unstructured":"A. Okabe , B. Boots , K. Sugihara , and S. N. Chiu . 1999 . Spatial Tessellations: Concepts and Applications of Voronoi Diagrams ( 2 nd ed.). John Wiley & Sons , Chichester . A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu. 1999. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams (2nd ed.). John Wiley & Sons, Chichester.","edition":"2"},{"key":"e_1_2_1_42_1","unstructured":"Packomania. 2014. Packomania Website. (2014). http:\/\/www.packomania.com\/cciuneq\/.  Packomania. 2014. Packomania Website. (2014). http:\/\/www.packomania.com\/cciuneq\/."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2459680"},{"key":"e_1_2_1_45_1","volume-title":"Roman A. Laskowski, Seong Eon Ryu, and Deok-Soo Kim.","author":"Ryu Joonghyun","year":"2016","unstructured":"Joonghyun Ryu , Mokwon Lee , Jehyun cha , Roman A. Laskowski, Seong Eon Ryu, and Deok-Soo Kim. 2016 . BetaSCPWeb: Side-chain prediction for protein structures using Voronoi diagrams and geometry prioritization. Nucleic Acids Research doi: 10.1093\/nar\/gkw368 (2016). 10.1093\/nar Joonghyun Ryu, Mokwon Lee, Jehyun cha, Roman A. Laskowski, Seong Eon Ryu, and Deok-Soo Kim. 2016. BetaSCPWeb: Side-chain prediction for protein structures using Voronoi diagrams and geometry prioritization. Nucleic Acids Research doi: 10.1093\/nar\/gkw368 (2016)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214034"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Royal Society 471","author":"Specht Eckard","year":"2016","unstructured":"Eckard Specht . 2016 . A precise algorithm to detect voids in polydisperse circle packings . Proceedings of the Royal Society 471 , 2182 (2016), 1--19. Eckard Specht. 2016. A precise algorithm to detect voids in polydisperse circle packings. Proceedings of the Royal Society 471, 2182 (2016), 1--19."},{"key":"e_1_2_1_48_1","volume-title":"Fundamentals E75-A","author":"Sugihara Kokichi","year":"1992","unstructured":"Kokichi Sugihara . 1992. A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction. IEICE Transactions , Fundamentals E75-A ( 1992 ), 468--477. Kokichi Sugihara. 1992. A simple method for avoiding numerical errors and degeneracy in Voronoi diagram construction. IEICE Transactions, Fundamentals E75-A (1992), 468--477."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/cgip.1993.1039"},{"key":"e_1_2_1_50_1","first-page":"380","article-title":"A solid modelling system free from topological inconsistency","volume":"12","author":"Sugihara Kokichi","year":"1989","unstructured":"Kokichi Sugihara and Masao Iri . 1989 . A solid modelling system free from topological inconsistency . Journal of Information Processing 12 , 4 (1989), 380 -- 393 . Kokichi Sugihara and Masao Iri. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4 (1989), 380--393.","journal-title":"Journal of Information Processing"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.163412"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000124"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167582"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195558"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2407404"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187890"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90016-E"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00040-2"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp599"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.09.001"},{"key":"e_1_2_1_61_1","unstructured":"Al Zimmermann. 2005. Al Zimmermann's programming Contest. (2005). http:\/\/recmath.com\/contest\/CirclePacking\/index.php.  Al Zimmermann. 2005. Al Zimmermann's programming Contest. (2005). http:\/\/recmath.com\/contest\/CirclePacking\/index.php."}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2939366","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2939366","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:56Z","timestamp":1750222556000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2939366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/2939366"],"URL":"https:\/\/doi.org\/10.1145\/2939366","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,16]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}