Exact Voronoi diagram for topographic spatial analysis

References

• Adikusuma, Y. Y., Z. Fang, and Y. He. 2020. “Fast Construction of Discrete Geodesic Graphs.” ACM Transactions on Graphics 39 (2): 1–19. Article 14. doi:10.1145/3144567.
   Web of Science ®Google Scholar
• Aronov, B., M. Berg, and S. Thite 2008. The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains. The 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. doi:10.1007/978-3-540-87744-8_9.
   Google Scholar
• Bobenko, A. I., and B. A. Springborn. 2007. “A Discrete Laplace–Beltrami Operator for Simplicial Surfaces.” Discrete & Computational Geometry 38 (4): 740–756. doi:10.1007/s00454-007-9006-1.
   Web of Science ®Google Scholar
• Bose, P., A. Maheshwari, C. Shu, and S. Wuhrer. 2011. “A Survey of Geodesic Paths on 3D Surfaces.” Computational Geometry 44 (9): 486–498. doi:https://doi.org/10.1016/j.comgeo.2011.05.006.
   Web of Science ®Google Scholar
• Chen, J. 1999. “A Raster-Based Method for Computing Voronoi Diagrams of Spatial Objects Using Dynamic Distance Transformation.” International Journal of Geographical Information Science 13 (3): 209–225. doi:10.1080/136588199241328.
   Web of Science ®Google Scholar
• Cheng, S. -W., T. K. Dey, and J. Shewchuk. 2012. Delaunay Mesh Generation. New York: Chapman & Hall/CRC.
   Google Scholar
• Chen, J., and Y. Han 1990. Shortest Paths on a Polyhedron. Proceedings of the sixth annual symposium on Computational geometry. Association for Computing Machinery, Berkley, California, USA, 360–369.
   Google Scholar
• Chen, Y., and Q. Zhou. 2013. “A Scale-Adaptive DEM for Multi-Scale Terrain Analysis.” International Journal of Geographical Information Science 27 (7): 1329–1348. doi:10.1080/13658816.2012.739690.
   Web of Science ®Google Scholar
• Crane, K., M. Livesu, E. Puppo, and Y. Qin 2020. A Survey of Algorithms for Geodesic Paths and Distances. https://ui.adsabs.harvard.edu/abs/2020arXiv200710430C.
   Google Scholar
• Crane, K., C. Weischedel, and M. Wardetzky. 2013. “Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow.” ACM Transactions on Graphics 32 (5): 152. doi:10.1145/2516971.2516977.
   Web of Science ®Google Scholar
• Du, Q., V. Faber, and M. Gunzburger. 1999. “Centroidal Voronoi Tessellations: Applications and Algorithms.” SIAM review 41 (4): 637–676. doi:10.1137/S0036144599352836.
   Web of Science ®Google Scholar
• Du, Q., M. Gunzburger, and Lili Ju. 2010. “Advances in Studies and Applications of Centroidal Voronoi Tessellations.” Numerical Mathematics: Theory, Methods and Applications 3 (2): 119–142. doi:10.4208/nmtma.2010.32s.1.
   Web of Science ®Google Scholar
• Dyn, N., D. Levin, and S. Rippa. 1990. “Data Dependent Triangulations for Piecewise Linear Interpolation.” Ima Journal of Numerical Analysis 10 (1): 137–154. doi:10.1093/imanum/10.1.137.
   Web of Science ®Google Scholar
• Elvidge, A. D., I. Sandu, N. Wedi, S. B. Vosper, A. Zadra, S. Boussetta, F. Bouyssel, A. van Niekerk, M. A. Tolstykh, and M. Ujiie. 2019. “Uncertainty in the Representation of Orography in Weather and Climate Models and Implications for Parameterized Drag.” Journal of Advances in Modeling Earth Systems 11 (8): 2567–2585. doi:10.1029/2019ms001661.
   Web of Science ®Google Scholar
• Gersho, A. 1979. “Asymptotically Optimal Block Quantization.” IEEE Transactions on Information Theory 25 (4): 373–380. doi:10.1109/TIT.1979.1056067.
   Web of Science ®Google Scholar
• Hafting, T., M. Fyhn, S. Molden, M. B. Moser, and E. I. Moser. 2005. “Microstructure of a Spatial Map in the Entorhinal Cortex.” Nature 436 (7052): 801–806. doi:10.1038/nature03721.
   PubMed Web of Science ®Google Scholar
• Herholz, P., and M. Alexa. 2018. “Factor Once: Reusing Cholesky Factorizations on Sub-Meshes.” ACM Transactions on Graphics 37 (6): 1–9. Article 230. doi:10.1145/3272127.3275107.
   Web of Science ®Google Scholar
• Herholz, P., F. Haase, and M. Alexa. 2017. “Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion.” Computer Graphics Forum 36 (2): 163–175. doi:https://doi.org/10.1111/cgf.13116.
   Web of Science ®Google Scholar
• Hu, H., X. Liu, and P. Hu. 2014. “Voronoi Diagram Generation on the Ellipsoidal Earth.” Computers & Geosciences 73: 81–87. doi:10.1016/j.cageo.2014.08.011.
   Web of Science ®Google Scholar
• Jacobson, A., and D. Panozzo 2018. Libigl: A Simple C++ Geometry Processing Library.
   Google Scholar
• Kanai, T., and H. Suzuki. 2001. “Approximate Shortest Path on a Polyhedral Surface and Its Applications.” Computer-Aided Design 33 (11): 801–811. doi:10.1016/S0010-4485(01)00097-5.
   Web of Science ®Google Scholar
• Kimmel, R., and J. A. Sethian. 1998. “Computing Geodesic Paths on Manifolds.” Proceedings of the National Academy of Sciences 95 (15): 8431–8435. doi:10.1073/pnas.95.15.8431.
   PubMed Web of Science ®Google Scholar
• Lanthier, M. A. 1999. Shortest path problems on polyhedral surfaces. Ph.D, Carleton University
   Google Scholar
• Liu, C. H. 2018. “A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon.” Algorithmica 82 (4): 915–937. doi:10.1007/s00453-019-00624-2.
   Web of Science ®Google Scholar
• Liu, Y. -J., Z. Chen, and K. Tang 2011. Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, 1502–1517, doi: 10.1109/TPAMI.2010.221.
   PubMed Web of Science ®Google Scholar
• Liu, Y. J., D. Fan, C. X. Xu, and Y. He. 2017. “Constructing Intrinsic Delaunay Triangulations from the Dual of Geodesic Voronoi Diagrams.” ACM Transactions on Graphics 36 (2): 43–57. doi:10.1145/2999532.
   Web of Science ®Google Scholar
• Liu, Y., M. F. Goodchild, Q. Guo, Y. Tian, and L. Wu. 2008. “Towards a General Field Model and Its Order in GIS.” International Journal of Geographical Information Science 22 (6): 623–643. doi:10.1080/13658810701587727.
   Web of Science ®Google Scholar
• Liu, Y. -J., Q. -Y. Zhou, and S. -M. Hu. 2007. “Handling Degenerate Cases in Exact Geodesic Computation on Triangle Meshes.” The Visual Computer 23 (9–11): 661–668. doi:10.1007/s00371-007-0136-5.
   Web of Science ®Google Scholar
• Mitchell, J. S. B., D. M. Mount, and C. H. Papadimitriou. 1987. “The Discrete Geodesic Problem.” Siam Journal on Computing 16 (4): 647–668. doi:10.1137/0216045.
   Web of Science ®Google Scholar
• Nazzaro, G., E. Puppo, and F. Pellacini. 2021. “geoTangle: Interactive Design of Geodesic Tangle Patterns on Surfaces.” ACM Transactions on Graphics 41 (2): 1–17. Article 12. doi:10.1145/3487909.
   Web of Science ®Google Scholar
• Okabe, A., B. Boots, K. Sugihara, and S. N. Chiu. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2 ed. Chichester: JOHN WILEY & SONS.
   Google Scholar
• Papadopoulou, E., and D. T. Lee. 1998. “A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains.” Algorithmica 20 (4): 319–352. doi:10.1007/PL00009199.
   Web of Science ®Google Scholar
• Peyré, G., and L. D. Cohen. 2006. “Geodesic Remeshing Using Front Propagation.” International Journal of Computer Vision 69 (1): 145–156. doi:10.1007/s11263-006-6859-3.
   Web of Science ®Google Scholar
• Qin, Y., X. Han, H. Yu, Y. Yu, and J. Zhang. 2016. “Fast and Exact Discrete Geodesic Computation Based on Triangle-Oriented Wavefront Propagation.” ACM Transactions on Graphics 35 (4): 125. doi:10.1145/2897824.2925930.
   Web of Science ®Google Scholar
• Qin, Y., H. Yu, and J. Zhang. 2017. “Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes.” Computer Graphics Forum 36 (5): 93–104. doi:https://doi.org/10.1111/cgf.13248.
   Web of Science ®Google Scholar
• Rivin, S. 1994. “Euclidean Structures on Simplicial Surfaces and Hyperbolic Volume.” Annals of Mathematics 139 (3): 553–580. doi:10.2307/2118572.
   Web of Science ®Google Scholar
• Shakhnarovich, G., T. Darrell, and P. Indyk. 2008. “Nearest-Neighbor Methods in Learning and Vision.” IEEE Transactions on Neural Networks 19 (2): 377–377. doi:10.1109/TNN.2008.917504
   Google Scholar
• Sharir, M., and A. Schorr. 1986. “On Shortest Paths in Polyhedral Spaces.” Siam Journal on Computing 15 (1): 193–215. doi:10.1137/0215014.
   Web of Science ®Google Scholar
• Sharp, N., Y. Soliman, and K. Crane. 2019. “The Vector Heat Method.” ACM transactions on graphics 38 (3): 24.21–24.19. doi:10.1145/3243651
   Web of Science ®Google Scholar
• Smith, M. W. 2014. “Roughness in the Earth Sciences.” Earth-Science Reviews 136: 202–225. doi:10.1016/j.earscirev.2014.05.016.
   Web of Science ®Google Scholar
• Stewart, C. W., and R. Ree. 2010. “A Voronoi Diagram Based Population Model for Social Species of Wildlife.” Ecological modelling 221 (12): 1554–1568. doi:10.1016/j.ecolmodel.2010.03.019.
   Web of Science ®Google Scholar
• Surazhsky, V., T. Surazhsky, D. Kirsanov, S. Gortler, and H. Hoppe. 2005. “Fast Exact and Approximate Geodesics on Meshes.” ACM Transactions on Graphics 24 (3): 553–560. doi:10.1145/1073204.1073228.
   Web of Science ®Google Scholar
• Wang, X., Z. Fang, J. Wu, S. Q. Xin, and Y. He. 2017. “Discrete Geodesic Graph (DGG) for Computing Geodesic Distances on Polyhedral Surfaces.” Computer Aided Geometric Design 52: 262–284. doi:10.1016/j.cagd.2017.03.010.
   Web of Science ®Google Scholar
• Xiang, Y., S. Q. Xin, and H. Ying. 2014. “Parallel Chen-Han (PCH) Algorithm for Discrete Geodesics.” ACM Transactions on Graphics 33: 1–11. doi:10.1145/2534161.
   Web of Science ®Google Scholar
• Xin, S. Q., and G. J. Wang. 2009. “Improving Chen and Han’s Algorithm on the Discrete Geodesic Problem.” ACM Transactions on Graphics 28 (4): 1–8. doi:10.1145/1559755.1559761.
   Web of Science ®Google Scholar
• Xin, S., W. Wang, Y. He, Y. Zhou, S. Chen, C. Tu, and Z. Shu. 2018. “Lightweight Preprocessing and Fast Query of Geodesic Distance via Proximity Graph.” Computer-Aided Design 102: 128–138. doi:10.1016/j.cad.2018.04.021.
   Web of Science ®Google Scholar
• Xu, C., Y. Liu, S. Qian, J. Li, and H. Ying. 2015. “Polyline-Sourced Geodesic Voronoi Diagrams on Triangle Meshes.” Computer Graphics Forum 33 (7): 161–170. doi:10.1111/cgf.12484.
   Web of Science ®Google Scholar
• Xu, C., T. Y. Wang, Y. J. Liu, L. Liu, and Y. He. 2015. “Fast Wavefront Propagation (FWP) for Computing Exact Geodesic Distances on Meshes.” IEEE Transactions on Visualization & Computer Graphics 21 (7): 822. doi:10.1109/TVCG.2015.2407404.
   PubMed Web of Science ®Google Scholar
• Ye, Z., R. Yi, M. Yu, Y. J. Liu, and Y. He. 2019. “Geodesic Centroidal Voronoi Tessellations: Theories.” Algorithms and Applications. doi:10.48550/arXiv.1907.00523.
   Google Scholar
• Ying, X., X. Wang, and Y. He. 2013. “Saddle Vertex Graph (SVG): A Novel Solution to the Discrete Geodesic Problem.” ACM Transactions on Graphics 32 (6): 1–12. doi:10.1145/2508363.2508379.
   Web of Science ®Google Scholar
• Zayer, R., D. Mlakar, M. Steinberger, and H. -P. Seidel. 2018. “Layered Fields for Natural Tessellations on Surfaces.” ACM Transactions on Graphics 37 (6): 1–15. Article 264. doi:10.1145/3272127.3275072.
   Web of Science ®Google Scholar