{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:18:27Z","timestamp":1743117507009,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031585340"},{"type":"electronic","value":"9783031585357"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-58535-7_25","type":"book-chapter","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T17:01:50Z","timestamp":1719939710000},"page":"296-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Fast and\u00a0Efficient Algorithm for\u00a0Construction of\u00a0Discrete Voronoi Diagram"],"prefix":"10.1007","author":[{"given":"Soumi","family":"Dhar","sequence":"first","affiliation":[]},{"given":"Shyamosree","family":"Pal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,3]]},"reference":[{"issue":"3","key":"25_CR1","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams-a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991). https:\/\/doi.org\/10.1145\/116873.116880","journal-title":"ACM Comput. Surv."},{"key":"25_CR2","volume-title":"Digital Geometry: Geometric Methods for Digital Picture Analysis","author":"R Klette","year":"2004","unstructured":"Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Publishers Inc., San Francisco (2004)"},{"key":"25_CR3","doi-asserted-by":"publisher","unstructured":"Wein, R., van den Berg, J.P.,\u00a0Halperin, D.: The visibility-voronoi complex and its applications, Computational Geometry 36(1), 66\u201387 (2007). special Issue on the 21st European Workshop on Computational Geometry. https:\/\/doi.org\/10.1016\/j.comgeo.2005.11.007. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0925772106000496","DOI":"10.1016\/j.comgeo.2005.11.007"},{"key":"25_CR4","doi-asserted-by":"publisher","unstructured":"Wang, X., et al.: Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes, Comput.-Aided Des. 58, 51\u201361 (2015). solid and Physical Modeling 2014. https:\/\/doi.org\/10.1016\/j.cad.2014.08.023. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0010448514001924","DOI":"10.1016\/j.cad.2014.08.023"},{"key":"25_CR5","doi-asserted-by":"publisher","unstructured":"Kim, D.S.: A single beta-complex solves all geometry problems in a molecule, pp. 254\u2013260 (2009). https:\/\/doi.org\/10.1109\/ISVD.2009.41","DOI":"10.1109\/ISVD.2009.41"},{"issue":"04","key":"25_CR6","doi-asserted-by":"publisher","first-page":"1250024","DOI":"10.1142\/S0219467812500246","volume":"12","author":"S Pal","year":"2012","unstructured":"Pal, S., Dutta, R., Bhowmick, P.: Circular arc segmentation by curvature estimation and geometric validation. Int. J. Image Graph. 12(04), 1250024 (2012). https:\/\/doi.org\/10.1142\/S0219467812500246","journal-title":"Int. J. Image Graph."},{"key":"25_CR7","doi-asserted-by":"publisher","unstructured":"She, B.,\u00a0Zhu, X.,\u00a0ye, X.,\u00a0Su, K.,\u00a0Lee, J.: Weighted network Voronoi diagrams for local spatial analysis. Comput. Environ. Urban Syst. 52, 70\u201380 (2015). https:\/\/doi.org\/10.1016\/j.compenvurbsys.2015.03.005","DOI":"10.1016\/j.compenvurbsys.2015.03.005"},{"issue":"01","key":"25_CR8","doi-asserted-by":"publisher","first-page":"2250008","DOI":"10.1142\/S0219467822500085","volume":"22","author":"S Dhar","year":"2022","unstructured":"Dhar, S., Pal, S.: Surface reconstruction: roles in the field of computer vision and computer graphics. Int. J. Image Graph. 22(01), 2250008 (2022). https:\/\/doi.org\/10.1142\/S0219467822500085","journal-title":"Int. J. Image Graph."},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"2025","DOI":"10.1109\/TVCG.2011.259","volume":"17","author":"N Lindow","year":"2011","unstructured":"Lindow, N., Baum, D., Hege, H.-C.: Voronoi-based extraction and visualization of molecular paths. IEEE Trans. Visual Comput. Graphics 17, 2025\u201334 (2011). https:\/\/doi.org\/10.1109\/TVCG.2011.259","journal-title":"IEEE Trans. Visual Comput. Graphics"},{"issue":"5","key":"25_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","volume":"9","author":"KQ Brown","year":"1979","unstructured":"Brown, K.Q.: Voronoi diagrams from convex hulls. Inf. Proc. Lett. 9(5), 223\u2013228 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90074-7","journal-title":"Inf. Proc. Lett."},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Shivanasab, P.,\u00a0Ali Abbaspour, R.: An incremental algorithm for simultaneous construction of 2D Voronoi diagram and Delaunay triangulation based on a face-based data structure. Adv. Eng. Softw. 169, 103129 (2022). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0965997822000400","DOI":"10.1016\/j.advengsoft.2022.103129"},{"key":"25_CR12","first-page":"14","volume":"30","author":"S Jida","year":"2017","unstructured":"Jida, S., Ouanan, M., Aksasse, B.: Color image segmentation using Voronoi diagram and 2D histogram. Int. J. Tomogr. Simul. 30, 14\u201320 (2017)","journal-title":"Int. J. Tomogr. Simul."},{"key":"25_CR13","unstructured":"\u0160eda, M.,\u00a0Pich, V.: Robot motion planning using generalised Voronoi diagrams. target 1 (2008) q2"},{"key":"25_CR14","doi-asserted-by":"publisher","unstructured":"Biswas, R.,\u00a0Bhowmick, P.: Construction of persistent Voronoi diagram on 3D digital plane, pp. 93\u2013104 (2017). https:\/\/doi.org\/10.1007\/978-3-319-59108-7_8","DOI":"10.1007\/978-3-319-59108-7_8"},{"key":"25_CR15","doi-asserted-by":"publisher","unstructured":"Zhao, S., Evans, T.M.,\u00a0Zhou, X.: Three-dimensional Voronoi analysis of monodisperse ellipsoids during triaxial shear. Powder Technol. 323, 323\u2013336 (2018). https:\/\/doi.org\/10.1016\/j.powtec.2017.10.023. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0032591017308197","DOI":"10.1016\/j.powtec.2017.10.023"},{"key":"25_CR16","doi-asserted-by":"publisher","unstructured":"Surajkanta, Y.,\u00a0Pal, S.: Recognition of spherical segments using number theoretic properties of Isothetic covers. Multimedia Tools Appl., 1\u201324 (2022). https:\/\/doi.org\/10.1007\/s11042-022-14182-3","DOI":"10.1007\/s11042-022-14182-3"},{"key":"25_CR17","doi-asserted-by":"publisher","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. In: Proceedings of the Second Annual Symposium on Computational Geometry, SCG \u201986. Association for Computing Machinery, New York, pp. 313-322 (1986). https:\/\/doi.org\/10.1145\/10515.10549","DOI":"10.1145\/10515.10549"},{"issue":"12","key":"25_CR18","doi-asserted-by":"publisher","first-page":"2149","DOI":"10.1109\/TVCG.2013.226","volume":"19","author":"N Ferreira","year":"2013","unstructured":"Ferreira, N., Poco, J., Vo, H.T., Freire, J., Silva, C.T.: Visual exploration of big Spatio-temporal urban data: a study of New York city taxi trips. IEEE Trans. Visual Comput. Graphics 19(12), 2149\u20132158 (2013). https:\/\/doi.org\/10.1109\/TVCG.2013.226","journal-title":"IEEE Trans. Visual Comput. Graphics"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M.,\u00a0Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd ed. Springer Cham (2008). https:\/\/www.worldcat.org\/oclc\/227584184","DOI":"10.1007\/978-3-540-77974-2"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-319-04483-5_15","volume-title":"Distributed Computing and Internet Technology","author":"D Saha","year":"2014","unstructured":"Saha, D., Das, N., Pal, S.: A digital-geometric approach for computing area coverage in wireless sensor networks. In: Natarajan, R. (ed.) Distributed Computing and Internet Technology, pp. 134\u2013145. Springer International Publishing, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04483-5_15"},{"key":"25_CR21","unstructured":"Allen, S.R.,\u00a0Barba, L.,\u00a0Iacono, J.,\u00a0Langerman, S.: Incremental Voronoi diagrams. CoRR abs\/1603.08485 (2016). http:\/\/arxiv.org\/abs\/1603.08485"},{"key":"25_CR22","doi-asserted-by":"publisher","unstructured":"Sherbrooke, E.,\u00a0Patrikalakis, N.,\u00a0Brisson, E.: Computation of the medial axis transform of 3-D Polyhedra (1995). https:\/\/doi.org\/10.1145\/218013.218059","DOI":"10.1145\/218013.218059"},{"issue":"03","key":"25_CR23","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1142\/S0218195998000187","volume":"08","author":"G Albers","year":"1998","unstructured":"Albers, G., Guibas, L.J., Mitchell, J.S.B., Roos, T.: Voronoi diagrams of moving points. Int. J. Comput. Geom. Appl. 08(03), 365\u2013379 (1998). https:\/\/doi.org\/10.1142\/S0218195998000187","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"25_CR24","series-title":"Computational Imaging and Vision","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/0-306-47025-X_36","volume-title":"Mathematical Morphology and its Applications to Image and Signal Processing","author":"A Meijster","year":"2002","unstructured":"Meijster, A., Roerdink, J., Hesselink, W.: A general algorithm for computing distance transforms in linear time. In: Goutsias, J., Vincent, L., Bloomberg, D.S. (eds.) Mathematical Morphology and its Applications to Image and Signal Processing. Computational Imaging and Vision, vol. 18, pp. 331\u2013340. Springer, Boston (2002). https:\/\/doi.org\/10.1007\/0-306-47025-X_36"},{"key":"25_CR25","doi-asserted-by":"publisher","unstructured":"Arora, S.,\u00a0Raghavan, P.,\u00a0Rao, S.: Approximation schemes for Euclidean k-medians and related problems. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC \u201998, pp. 106-113. Association for Computing Machinery, New York (1998). https:\/\/doi.org\/10.1145\/276698.276718","DOI":"10.1145\/276698.276718"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.N.,\u00a0Mathieu, C.: A polynomial-time approximation scheme for euclidean steiner forest (2015)","DOI":"10.1145\/2629654"},{"issue":"02","key":"25_CR27","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1142\/S0218195994000124","volume":"04","author":"K Sugihara","year":"1994","unstructured":"Sugihara, K., Iri, M.: A robust topology-oriented incremental algorithm for Voronoi diagrams. Int. J. Comput. Geom. Appl. 04(02), 179\u2013228 (1994). https:\/\/doi.org\/10.1142\/S0218195994000124","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"25_CR28","doi-asserted-by":"publisher","unstructured":"Hoff, K.E.,\u00a0Keyser, J.,\u00a0Lin, M.,\u00a0Manocha, D.,\u00a0Culver, T.: Fast computation of generalized Voronoi diagrams using graphics hardware. In: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH \u201999. ACM Press\/Addison-Wesley Publishing Co., USA, pp. 277\u2013286 (1999). https:\/\/doi.org\/10.1145\/311535.311567","DOI":"10.1145\/311535.311567"},{"key":"25_CR29","doi-asserted-by":"publisher","unstructured":"Rong, G., Tan, T.-S.: Jump flooding in GPU with applications to Voronoi diagram and distance transform, vol. 2006, pp. 109\u2013116 (2006). https:\/\/doi.org\/10.1145\/1111411.1111431","DOI":"10.1145\/1111411.1111431"},{"key":"25_CR30","doi-asserted-by":"publisher","unstructured":"Masood, T.B., Malladi, H.K.,\u00a0Natarajan, V.: Facet-JFA: faster computation of discrete Voronoi diagrams. In: Proceedings of the 2014 Indian Conference on Computer Vision Graphics and Image Processing, ICVGIP \u201914. Association for Computing Machinery, New York (2014). https:\/\/doi.org\/10.1145\/2683483.2683503","DOI":"10.1145\/2683483.2683503"},{"key":"25_CR31","doi-asserted-by":"publisher","unstructured":"Bhowmick, P., Bhattacharya, B.B.: Number-theoretic interpretation and construction of a digital circle. Discr. Appl. Math. 156(12), 2381\u20132399 (2008). https:\/\/doi.org\/10.1016\/j.dam.2007.10.022. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X07004817","DOI":"10.1016\/j.dam.2007.10.022"},{"key":"25_CR32","doi-asserted-by":"publisher","unstructured":"Bera, S.,\u00a0Bhowmick, P.,\u00a0Bhattacharya, B.: On the characterization of absentee-voxels in a spherical surface and volume of revolution in $${\\mathbb{z}}^3$$ z 3. J. Math. Imaging Vision 56 (2016). https:\/\/doi.org\/10.1007\/s10851-016-0654-8","DOI":"10.1007\/s10851-016-0654-8"},{"key":"25_CR33","doi-asserted-by":"publisher","unstructured":"Andres, E.,\u00a0Richaume, L.,\u00a0Largeteau-Skapin, G.: Digital surface of revolution with hand-drawn generatrix. J. Math. Imaging Vis. (2017). https:\/\/doi.org\/10.1007\/s10851-017-0708-6","DOI":"10.1007\/s10851-017-0708-6"},{"issue":"5","key":"25_CR34","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/0097-8493(94)90164-3","volume":"18","author":"E Andres","year":"1994","unstructured":"Andres, E.: Discrete circles, rings and spheres. Comput. Graph. 18(5), 695\u2013706 (1994). https:\/\/doi.org\/10.1016\/0097-8493(94)90164-3","journal-title":"Comput. Graph."}],"container-title":["Communications in Computer and Information Science","Computer Vision and Image Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-58535-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T17:08:09Z","timestamp":1719940089000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-58535-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031585340","9783031585357"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-58535-7_25","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare that there is no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}},{"value":"CVIP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Vision and Image Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jammu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 November 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 November 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cvip2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iitjammu.ac.in\/cvip2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Online CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"461","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"140","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}