{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:42:44Z","timestamp":1760060564323,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T00:00:00Z","timestamp":1756857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Voronoi partitioning is a fundamental geometric concept with applications across computational geometry, robotics, optimization, and resource allocation. While Euclidean distance is the most commonly used metric, alternative distance functions can significantly influence the shape and properties of Voronoi cells. This paper presents a comprehensive mathematical analysis of various distance metrics used in Voronoi partitioning, including Euclidean, Manhattan, Minkowski, weighted, anisotropic, and geodesic metrics. We analyze their mathematical formulations, geometric properties, topological implications, and computational complexity. This work aims to provide a theoretical framework for selecting appropriate metrics for Voronoi-based modeling in diverse applications.<\/jats:p>","DOI":"10.3390\/computation13090212","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T12:07:32Z","timestamp":1756901252000},"page":"212","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Metric-Driven Voronoi Diagrams: A Comprehensive Mathematical Framework"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0599-748X","authenticated-orcid":false,"given":"Vishnu G.","family":"Nair","sequence":"first","affiliation":[{"name":"Aeronautical and Automobile Engineering, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Udupi 576104, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Maruani, N., Klokov, R., Ovsjanikov, M., Alliez, P., and Desbrun, M. (2023). VoroMesh: Learning Watertight Surface Meshes with Voronoi Diagrams. arXiv.","DOI":"10.1109\/ICCV51070.2023.01339"},{"key":"ref_2","unstructured":"Sikorski, A., and Heida, M. (2024). Voronoi Graph: Improved Raycasting and Integration Schemes for High-Dimensional Voronoi Diagrams. arXiv."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Zhou, M., Li, J., Wang, C., Wang, J., and Wang, L. (2024). Applications of Voronoi Diagrams in Multi-Robot Coverage: A Review. J. Mar. Sci. Eng., 12.","DOI":"10.3390\/jmse12061022"},{"key":"ref_4","first-page":"111","article-title":"An Efficient Algorithm for Approximate Voronoi Diagram Construction on Triangulated Surfaces","volume":"9","author":"Meng","year":"2023","journal-title":"Comput. Vis. Media"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Vicidomini, M., L\u00e9v\u00eaque-Fort, S., Sibarita, J.B., and Levet, L. (2023). Optimizing Voronoi-Based Quantifications for Reaching Interactive Analysis of 3D Localizations in the Million Range. Front. Bioinform., 3.","DOI":"10.3389\/fbinf.2023.1249291"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1017\/S0263574719001127","article-title":"GM-VPC: An Algorithm for Multi-robot Coverage of Known Spaces Using Generalized Voronoi Partition","volume":"38","author":"Nair","year":"2020","journal-title":"Robotica"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"45","DOI":"10.22436\/jmcs.038.01.04","article-title":"Best Proximity Point Results on R-Metric Spaces with Applications to Fractional Differential Equation and Production-Consumption Equilibrium","volume":"38","author":"Janardhanan","year":"2025","journal-title":"J. Math. Comput. Sci."},{"key":"ref_8","first-page":"1","article-title":"Fixed Point Theorems Over Extended (\u03d5, \u03c8)-Metric Spaces and Applications in Differential Equations","volume":"2024","author":"Taleb","year":"2024","journal-title":"J. Funct. Spaces"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Karimizad, S.S., and Rad, G.S. (2024). Pre-Symmetric w-Cone Distances and Characterization of TVS-Cone Metric Completeness. Mathematics, 12.","DOI":"10.3390\/math12121833"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.26713\/cma.v14i2.2083","article-title":"A Survey on Branciari Metric Spaces","volume":"14","author":"Das","year":"2023","journal-title":"Commun. Math. Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/s00039-024-00658-x","article-title":"A Metric Fixed Point Theorem and Some of Its Applications","volume":"34","author":"Karlsson","year":"2024","journal-title":"Geom. Funct. Anal."},{"key":"ref_12","first-page":"993","article-title":"On Banach\u2019s Fixed Point Theorem in Perturbed Metric Spaces","volume":"15","author":"Jleli","year":"2025","journal-title":"J. Appl. Anal. Comput."},{"key":"ref_13","unstructured":"D\u00edaz, A.E., Hogan, E., Illingworth, F., Michel, L., Portier, J., and Yan, J. (2024). Exponential Odd-Distance Sets under the Manhattan Metric. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lim, E.U. (2023). Quasi Manhattan Wasserstein Distance. arXiv.","DOI":"10.21203\/rs.3.rs-3893219\/v1"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1134\/S0001434624030362","article-title":"On Locally Chebyshev Sets","volume":"115","author":"Shklyaev","year":"2024","journal-title":"Math. Notes"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1134\/S1061920823010107","article-title":"Estimates of the Chebyshev Radius in Terms of the MAX-Metric Function and the MAX-Projection Operator","volume":"30","year":"2023","journal-title":"Russ. J. Math. Phys."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1119\/5.0214271","article-title":"Hyperbolic Times in Minkowski Space","volume":"92","year":"2024","journal-title":"Am. J. Phys."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1875","DOI":"10.1007\/s10910-021-01266-y","article-title":"Extended Minkowski Spaces, Zero Norms, and Minkowski Hypersurfaces","volume":"59","year":"2021","journal-title":"J. Math. Chem."},{"key":"ref_19","first-page":"6161839","article-title":"Approximating Fixed Points of Enriched Nonexpansive Mappings in Geodesic Spaces","volume":"2022","author":"Shukla","year":"2022","journal-title":"J. Funct. Spaces"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1642","DOI":"10.1017\/etds.2016.106","article-title":"Fixed Point Theorems for Metric Spaces with a Conical Geodesic Bicombing","volume":"38","author":"Basso","year":"2018","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Baumann, T., and Mallot, H.A. (2023). Metric Information in Cognitive Maps: Euclidean Embedding of Non-Euclidean Environments. PLoS Comput. Biol., 19.","DOI":"10.1101\/2023.06.09.544331"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Esfandiari, H., Mirrokni, V., and Narayanan, S. (2022). Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets. arXiv.","DOI":"10.1145\/3519935.3520011"},{"key":"ref_23","first-page":"271","article-title":"Comparative Analysis Between Euclidean Distance Metric and Mahalanobis Distance Metric","volume":"12","author":"Kumari","year":"2024","journal-title":"Int. J. Innov. Res. Technol. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"587","DOI":"10.4236\/jmp.2018.95052","article-title":"On the Existence of Non-Intersecting Straight Lines on the Plane","volume":"9","author":"Chubykalo","year":"2018","journal-title":"J. Mod. Phys."},{"key":"ref_25","first-page":"937","article-title":"A Euclidean-Like Discrete Spacetime from the Unification of a Multitude of Hypercubic Lattices","volume":"8","year":"2017","journal-title":"J. Mod. Phys."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"\u00c7iner, A., Erg\u00fcler, Z.A., Bezzeghoud, M., Ustuner, M., Eshagh, M., El-Askary, H., Biswas, A., Gasperini, L., Hinzen, K.-G., and Karakus, M. (2024). Fortune\u2019s Algorithm for Calculating the Voronoi Diagram of Polylines, Polygons, and Functions. Recent Research on Geotechnical Engineering, Remote Sensing, Geophysics and Earthquake Seismology, Springer. Advances in Science, Technology & Innovation.","DOI":"10.1007\/978-3-031-43218-7"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1945","DOI":"10.51519\/journalisi.v6i3.841","article-title":"Manhattan Metric in K-Means Clustering for Data Grouping","volume":"6","author":"Sari","year":"2024","journal-title":"J. Inf. Syst. Inform."},{"key":"ref_28","first-page":"1","article-title":"Robust linear regression for high-dimensional data: An overview","volume":"23","author":"Filzmoser","year":"2020","journal-title":"Adv. Rev."},{"key":"ref_29","first-page":"109607","article-title":"AIDA: Analytic isolation and Distance based anomaly detection algorithm","volume":"141","author":"Arias","year":"2023","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1109\/COMST.2014.2336610","article-title":"A Survey of Distance and Similarity Measures Used Within Network Intrusion Anomaly Detection","volume":"17","author":"Borghetti","year":"2015","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"72778","DOI":"10.1109\/ACCESS.2025.3564185","article-title":"Efficient Computation of the K Nearest Neighbors Query Using Incremental Radius on a k2-tree","volume":"13","year":"2025","journal-title":"IEEE Access"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.ins.2021.10.048","article-title":"Adaptive Explicit Kernel Minkowski Weighted K-means","volume":"584","author":"Aradnia","year":"2022","journal-title":"Inf. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1016\/j.patcog.2011.08.012","article-title":"Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering","volume":"45","author":"Mirkin","year":"2012","journal-title":"Pattern Recognit."},{"key":"ref_34","unstructured":"Bozkurt, E., and Ortega, A. (2025). Robust Classification under Noisy Labels: A Geometry-Aware Reliability Framework for Foundation Models. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Patel, B., Yadav, k., and Ghosh, D. (2020, January 16\u201317). State-of-Art: Similarity Assessment for Content Based Image Retrieval System. Proceedings of the 2020 IEEE International Symposium on Sustainable Energy, Signal Processing and Cyber Security (iSSSC), Gunupur Odisha, India.","DOI":"10.1109\/iSSSC50941.2020.9358899"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L. (2006). Nearest-Neighbor Searching and Metric Space Dimensions. Neural Information Processing Series, MIT Press.","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Chen, B.Y., Huang, H., Chen, H.-P., Liu, W., Chen, X.-Y., and Jia, T. (2023). Efficient Algorithm for Constructing Order K Voronoi Diagrams in Road Networks. ISPRS Int. J. Geo.-Inf., 12.","DOI":"10.3390\/ijgi12040172"},{"key":"ref_38","unstructured":"Zehui, X., and Muqing, W. (2021, January 10\u201313). Optimized Weighted Voronoi-Based Clustering for Wireless Sensor Networks. Proceedings of the 7th International Conference on Computer and Communications (ICCC), Chengdu, China."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Riol, E., Puche, J.C., Delgado, F.J., Finat, J., and Martinez, R. (2011, January 28\u201330). Weighted Voronoi Diagrams for Optimal Location of Goods and Services in Planar Maps. Proceedings of the 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering, Qingdao, China.","DOI":"10.1109\/ISVD.2011.27"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1177\/15501477211069903","article-title":"Multiplicatively weighted Voronoi-based sensor collaborative redeployment in software-defined wireless sensor networks","volume":"18","author":"Wang","year":"2022","journal-title":"Int. J. Distrib. Sens. Netw."},{"key":"ref_41","first-page":"1","article-title":"Anisotropic Metric Learning for Improved Image Segmentation","volume":"121","author":"Giacomini","year":"2022","journal-title":"IEEE Trans. Image Process."},{"key":"ref_42","unstructured":"Naden, E., M\u00e4rz, T., and Macdonald, C.B. (2014). Anisotropic Diffusion on Curved Surfaces. arXiv."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"19162","DOI":"10.1109\/ACCESS.2022.3149520","article-title":"Multiscale Anisotropic Morphological Directional Derivatives for Noise-Robust Image Edge Detection","volume":"10","author":"Yu","year":"2022","journal-title":"IEEE Access"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3390\/modelling1010001","article-title":"Time Series Clustering: A Complex Network-Based Approach for Feature Selection in Multi-Sensor Data","volume":"1","author":"Bonacina","year":"2020","journal-title":"Modelling"},{"key":"ref_45","first-page":"19","article-title":"Optimal path planning using a continuous anisotropic model for navigation on irregular terrains","volume":"16","year":"2022","journal-title":"Intell. Serv. Robot."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"131617","DOI":"10.1016\/j.jhydrol.2024.131617","article-title":"Manifold embedding based on geodesic distance for nonstationary spatial estimation in higher dimensions","volume":"640","author":"Park","year":"2024","journal-title":"J. Hydrol."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Gattone, S.A., De Sanctis, A., Puechmorel, S., and Nicol, F. (2018). On the Geodesic Distance in Shapes K-means Clustering. Entropy, 20.","DOI":"10.3390\/e20090647"},{"key":"ref_48","first-page":"1","article-title":"Geodesic Distance on Riemannian Manifold using Jacobi Iterations in 3D Face Recognition System","volume":"6","author":"Ahdid","year":"2017","journal-title":"Int. J. Inform. Commun. Technol. (IJ-ICT)"},{"key":"ref_49","unstructured":"Geng, C., Wang, J., Chen, L., Bao, W., Chu, C., and Gao, Z. (2020). Uniform Interpolation Constrained Geodesic Learning on Data Manifold. arXiv."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"450","DOI":"10.3390\/automation5030026","article-title":"Fast and Efficient Drone Path Planning Using Riemannian Manifold in Indoor Environment","volume":"5","author":"Dujari","year":"2024","journal-title":"Automation"},{"key":"ref_51","unstructured":"Sutti, M. (2023). Shooting methods for computing geodesics on the Stiefel manifold. arXiv."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"2217","DOI":"10.1109\/TAC.2013.2254619","article-title":"Stochastic Gradient Descent on Riemannian Manifolds","volume":"58","author":"Bonnabel","year":"2013","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Akian, M., Gaubert, S., and Liu, S. (2024). A Multi-Level Fast-Marching Method For The Minimum Time Problem. arXiv.","DOI":"10.1137\/23M1563657"},{"key":"ref_54","unstructured":"Khan, M.A. (2025, August 06). A Comprehensive Study of Dijkstra\u2019s Algorithm. Available online: https:\/\/ssrn.com\/abstract=4559304."}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/9\/212\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:38:36Z","timestamp":1760035116000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/9\/212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,3]]},"references-count":54,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["computation13090212"],"URL":"https:\/\/doi.org\/10.3390\/computation13090212","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2025,9,3]]}}}