{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T09:45:02Z","timestamp":1753868702835,"version":"3.41.2"},"reference-count":31,"publisher":"Wiley","issue":"11","license":[{"start":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T00:00:00Z","timestamp":1705363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2024,5,15]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>Voronoi diagram is a versatile geometric structure used in solving many computational geometry problems in the field of image analysis, computer vision, engineering, medicine, molecular biology and various other disciplines. As a result it is a popular research domain. The literature boasts of many elegant and efficient methods for the construction of the Voronoi diagram in the real space. But these algorithms often fail to perform well when applied to the discrete domain. We present in this paper a novel algorithm for the construction of discrete Voronoi diagram using digital geometric concepts that takes care of the geometric perspective of the Voronoi diagram in the discrete domain. Although our technique is more suited for the CPU but by careful use of some cut\u2010off heuristics we are able to design a parallel programming approach for the construction of the Voronoi diagram making use of the GPU computational power. The speedup of our algorithm is compatible with the popular GPU technique for Voronoi diagram construction, namely, Jump flood algorithm. But since our algorithm uses the geometric perspective for the construction of Voronoi diagram it gives more accurate output and hence requires no correction step as is the case for the Jump flood algorithm. Furthermore, our approach focuses on extensibility, allowing for easy amenability for construction of higher dimensional Voronoi diagram. This ensures that the Voronoi diagram generation process can be adapted and expanded upon to meet specific requirements or incorporate future enhancements. We present an implementation of the proposed algorithm on a GPU using TAICHI language and describe its performance benefits on multiple input sites.<\/jats:p>","DOI":"10.1002\/cpe.8018","type":"journal-article","created":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T03:58:55Z","timestamp":1705463935000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A digital geometric approach for discrete Voronoi diagram construction using GPU"],"prefix":"10.1002","volume":"36","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-4407-3079","authenticated-orcid":false,"given":"Soumi","family":"Dhar","sequence":"first","affiliation":[{"name":"Department of CSE National Institute of Technology Silchar  Assam India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shyamosree","family":"Pal","sequence":"additional","affiliation":[{"name":"Department of CSE National Institute of Technology Silchar  Assam India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaurav","family":"Bhattacharjee","sequence":"additional","affiliation":[{"name":"Department of CSE National Institute of Technology Silchar  Assam India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhishek","family":"Pandey","sequence":"additional","affiliation":[{"name":"Department of CSE National Institute of Technology Silchar  Assam India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2024,1,16]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"volume-title":"Digital Geometry: Geometric Methods for Digital Picture Analysis","year":"2004","author":"Klette R","key":"e_1_2_9_3_1"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.11.007"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.08.023"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVD.2009.41"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219467812500246"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.259"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.advengsoft.2022.103129"},{"key":"e_1_2_9_10_1","first-page":"14","article-title":"Color image segmentation using Voronoi diagram and 2D histogram","volume":"30","author":"Jida S","year":"2017","journal-title":"Int J Tomography Simulat"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2015.03.005"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219467822500085"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04483-5_15"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020\u20100190(79)90074\u20107"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2022.103374"},{"journal-title":"CoRR","article-title":"Incremental Voronoi diagrams","author":"Allen SR","key":"e_1_2_9_16_1"},{"key":"e_1_2_9_17_1","doi-asserted-by":"crossref","unstructured":"SherbrookeE PatrikalakisN BrissonE.Computation of the medial axis transform of 3\u2010d polyhedra.1995. doi:10.1145\/218013.218059","DOI":"10.1145\/218013.218059"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195998000187"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/10515.10549"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978\u20103\u2010642\u201054423\u20101_9"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2005.11.001"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/1049\u20109660(92)90050\u2010D"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/1049\u20109652(92)90072\u20106"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111431"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2683483.2683503"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311567"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851\u2010016\u20100654\u20108"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.10.022"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.07.036"},{"key":"e_1_2_9_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851\u2010017\u20100708\u20106"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1524\u20100703(03)00004\u20103"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000124"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.8018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,24]],"date-time":"2024-04-24T07:30:27Z","timestamp":1713943827000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.8018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,16]]},"references-count":31,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,5,15]]}},"alternative-id":["10.1002\/cpe.8018"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/cpe.8018","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2024,1,16]]},"assertion":[{"value":"2023-05-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e8018"}}