References(68)
[1]
Tsai, J.; Gerstein, M.; Levitt, M. Simulating the minimum core for hydrophobic collapse in globular proteins. Protein Science Vol. 6, No. 12, 2606–2616, 1997.
[2]
Liu, Y. J.; Yu, M. J.; Li, B. J.; He, Y. Intrinsic manifold SLIC: A simple and efficient method for computing content-sensitive superpixels. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 40, No. 3, 653–666, 2018.
[3]
Dong, X.; Chen, Z. G.; Liu, Y. J.; Yao, J. F.; Guo, X. H. GPU-based supervoxel generation with a novel anisotropic metric. IEEE Transactions on Image Processing Vol. 30, 8847–8860, 2021.
[4]
Liu, Y.; Wang, W. P.; Lévy, B.; Sun, F.; Yan, D. M.; Lu, L.; Yang, C. On centroidal Voronoi tessellation—Energy smoothness and fast computation. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 101, 2009.
[5]
Liu, Y. J.; Xu, C. X.; Yi, R.; Fan, D.; He, Y. Manifold differential evolution (MDE). ACM Transactions on Graphics Vol. 35, No. 6, Article No. 243, 2016.
[6]
Wang, X. N.; Ying, X.; Liu, Y. J.; Xin, S. Q.; Wang, W. P.; Gu, X. F.; Mueller-Wittig, W.; He, Y. Intrinsic computation of centroidal voronoi tessellation (CVT) on meshes. Computer-Aided Design Vol. 58, 51–61, 2015.
[7]
Stanković T.; Shea, K. Investigation of a Voronoi diagram representation for the computational design of additively manufactured discrete lattice structures. Journal of Mechanical Design Vol. 142, No. 11, 111704, 2020.
[8]
Dai, G. Y.; Lv, H. X.; Chen, L. Y.; Zhou, B. B.; Xu, P. A novel coverage holes discovery algorithm based on Voronoi diagram in wireless sensor networks. International Journal of Hybrid Information Technology Vol. 9, No. 3, 273–282, 2016.
[9]
Boissonnat, J. D.; Wormser, C.; Yvinec, M. Curved Voronoi diagrams. In: Effective Computational Geome-try for Curves and Surfaces. Berlin Heidelberg: Springer, 67–116, 2006.
[10]
Aurenhammer, F. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Computing Surveys Vol. 23, No. 3, 345–405, 1991.
[11]
Liu, J.; Liu, S. A survey on applications of Voronoi diagrams. Journal of Engineering Graphics Vol. 22, No. 2, 125–132, 2004.
[12]
Kunze, R.; Wolter, F. E.; Rausch, T. Geodesic Voronoi diagrams on parametric surfaces. Proceedings Computer Graphics International Vol. 16, No. 3, 230–237, 1997.
[13]
Liu, Y. J.; Chen, Z. Q.; Tang, K. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 8, 1502–1517, 2011.
[14]
Qin, Y. P.; Yu, H. C.; Zhang, J. J. Fast and memory-efficient Voronoi diagram construction on triangle meshes. Computer Graphics Forum Vol. 36, No. 5, 93–104, 2017.
[15]
Na, H. S.; Lee, C. N.; Cheong, O. Voronoi diagrams on the sphere. Computational Geometry Vol. 23, No. 2, 183–194, 2002.
[16]
Onishi, K.; Takayama, N. Construction of Voronoi diagram on the upper half-plane. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences Vol. E79-A, No. 4, 533–539, 1996.
[17]
Medimegh, N.; Belaid, S.; Werghi, N. A survey of the 3D triangular mesh watermarking techniques. International Journal of Multimedia Vol. 1, No. 1, 33–39, 2015.
[18]
Peyré, G.; Cohen, L. D. Geodesic remeshing using front propagation. International Journal of Computer Vision Vol. 69, No. 1, 145–156, 2006.
[19]
Peethambaran, J.; Muthuganapathy, R. Reconstruction of water-tight surfaces through Delaunay sculpting. Computer-Aided Design Vol. 58, 62–72, 2015.
[20]
Kimmel, R.; Kiryati, N.; Bruckstein, A. M. Multivalued distance maps for motion planning on surfaces with moving obstacles. IEEE Transactions on Robotics and Automation Vol. 14, No. 3, 427–436, 1998.
[21]
Lu, L.; Lévy, B.; Wang, W. P. Centroidal Voronoi tessellation of line segments and graphs. Computer Graphics Forum Vol. 31, No. 2pt4, 775–784, 2012.
[22]
Mitchell, J. S. B.; Mount, D. M.; Papadimitriou, C. H. The discrete geodesic problem. SIAM Journal on Computing Vol. 16, No. 4, 647–668, 1987.
[23]
Qin, Y. P.; Han, X. G.; Yu, H. C.; Yu, Y. Z.; Zhang, J. J. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation. ACM Transactions on Graphics Vol. 35, No. 4, Article No. 125, 2016.
[24]
Xu, C. X.; Liu, Y. J.; Sun, Q.; Li, J. Y.; He, Y. Polyline-sourced geodesic Voronoi diagrams on triangle meshes. Computer Graphics Forum Vol. 33, No. 7, 161–170, 2014.
[25]
Bose, P.; Maheshwari, A.; Shu, C.; Wuhrer, S. A survey of geodesic paths on 3D surfaces. Computational Geometry Vol. 44, No. 9, 486–498, 2011.
[26]
Crane, K.; Livesu, M.; Puppo, E.; Qin, Y. P. A survey of algorithms for geodesic paths and distances. arXiv preprint arXiv:2007.10430, 2020.
[27]
Surazhsky, V.; Surazhsky, T.; Kirsanov, D.; Gortler, S. J.; Hoppe, H. Fast exact and approximate geodesics on meshes. ACM Transactions on Graphics Vol. 24, No. 3, 553–560, 2005.
[28]
Chen, J. D.; Han, Y. J. Shortest paths on a polyhedron. In: Proceedings of the 6th Annual Symposium on Computational Geometry, 360–369, 1990.
[29]
Xin, S. Q.; Wang, G. J. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 104, 2009.
[30]
Ying, X.; Xin, S. Q.; He, Y. Parallel Chen–Han (PCH) algorithm for discrete geodesics. ACM Transactions on Graphics Vol. 33, No. 1, Article No. 9, 2014.
[31]
Xu, C. X.; Wang, T. Y.; Liu, Y. J.; Liu, L. G.; He, Y. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Transactions on Visualization and Computer Graphics Vol. 21, No. 7, 822–834, 2015.
[32]
Du, J.; He, Y.; Fang, Z.; Meng, W. L.; Xin, S. Q. On the vertex-oriented triangle propagation (VTP) algorithm: Parallelization and approximation. Computer-Aided Design Vol. 130, 102943, 2021.
[33]
Kimmel, R.; Sethian, J. A. Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences of the United States of America Vol. 95, No. 15, 8431–8435, 1998.
[34]
Weber, O.; Devir, Y. S.; Bronstein, A. M.; Bronstein, M. M.; Kimmel, R. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Transactions on Graphics Vol. 27, No. 4, Article No. 104, 2008.
[35]
Crane, K.; Weischedel, C.; Wardetzky, M. Geodesics in heat. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 152, 2013.
[36]
Solomon, J.; Rustamov, R.; Guibas, L.; Butscher, A. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics Vol. 33, No. 4, Article No. 67, 2014.
[37]
Xin, S. Q.; Ying, X.; He, Y. Constant-time all-pairs geodesic distance query on triangle meshes. In: Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 31–38, 2012.
[38]
Ying, X.; Wang, X. N.; He, Y. Saddle vertex graph (SVG). ACM Transactions on Graphics Vol. 32, No. 6, Article No. 170, 2013.
[39]
Lanthier, M.; Maheshwari, A.; Sack, J.-R. Approxi-mating shortest paths on weighted polyhedral surfaces. Algorithmica Vol. 30, No. 4, 527–562, 2001.
[40]
Lanthier, M.; Maheshwari, A.; Sack, J. R. Approxi-mating weighted shortest paths on polyhedral surfaces. In: Proceedings of the 13th Annual Symposium on Computational Geometry, 274–283, 1997.
[41]
Aleksandrov, L.; Lanthier, M.; Maheshwari, A.; Sack, J. R. An ε-approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Algorithm Theory — SWAT’98. Lecture Notes in Computer Science, Vol. 1432. Arnborg, S.; Ivansson, L. Eds. Springer Berlin Heidelberg, 11–22, 1998.
[42]
Aleksandrov, L.; Maheshwari, A.; Sack, J. R. Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM Vol. 52, No. 1, 25–53, 2005.
[43]
Adikusuma, Y. Y.; Du, J.; Fang, Z.; He, Y. An accuracy controllable and memory efficient method for computing high-quality geodesic distances on triangle meshes. Computer-Aided Design Vol. 150, 103333, 2022.
[44]
Adikusuma, Y. Y.; Fang, Z.; He, Y. Fast construction of discrete geodesic graphs. ACM Transactions on Graphics Vol. 39, No. 2, Article No. 14, 2020.
[45]
Aleksandrov, L.; Maheshwari, A.; Sack, J. R. Approximation algorithms for geometric shortestpath problems. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 286–295, 2000.
[46]
Meng, W. L.; Xin, S. Q.; Tu, C. H.; Chen, S. M.; He, Y.; Wang, W. P. Geodesic tracks: Computing discrete geodesics with track-based Steiner point propagation. IEEE Transactions on Visualization and Computer Graphics Vol. 28, No. 12, 4887–4901, 2022.
[47]
Lee, D. T. Medial axis transformation of a planar shape. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. PAMI-4, No. 4, 363–369, 1982.
[48]
Giblin, P.; Kimia, B. B. A formal classification of 3D medial axis points and their local geometry. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 26, No. 2, 238–251, 2004.
[49]
Leibon, G.; Letscher, D. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In: Proceedings of the 16th Annual Symposium on Computational Geometry, 341–349, 2000.
[50]
Boissonnat, J. D.; Dyer, R.; Ghosh, A. Constructing intrinsic Delaunay triangulations of submanifolds. arXiv preprint arXiv:1303.6493, 2013.
[51]
Augenbaum, J. M.; Peskin, C. S. On the construction of the Voronoi mesh on a sphere. Journal of Computational Physics Vol. 59, No. 2, 177–192, 1985.
[52]
Senechal, M. Spatial tessellations: Concepts and applications of Voronoi diagrams. Science Vol. 260, No. 5111, 1170–1173, 1993.
[53]
Kimmel, R.; Sethian, J. A. Fast Voronoi diagrams and offsets on triangulated surfaces. Technical Report. Technion-Israel Inst of Tech Haifa Dept of Computer Science, 2000.
[54]
Liu, Y. J.; Tang, K. The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces. Information Processing Letters Vol. 113, No. 4, 132–136, 2013.
[55]
Liu, Y. J.; Fan, D.; Xu, C. X.; He, Y. Constructing intrinsic Delaunay triangulations from the dual of geodesic Voronoi diagrams. ACM Transactions on Graphics Vol. 36, No. 2, Article No. 15, 2017.
[56]
Van Kreveld, M.; Schwarzkopf, O.; de Berg, M.; Overmars, M. Computational geometry algorithms and applications. Computer Graphics Forum Vol. 13, No. 3, 12–16, 2000.
[57]
Rong, G. D.; Liu, Y.; Wang, W. P.; Yin, X. T.; Gu, D.; Guo, X. H. GPU-assisted computation of centroidal Voronoi tessellation. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 3, 345–356, 2011.
[58]
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing Vol. 16, No. 1, 78–96, 1987.
[59]
Gavrilova, M.; Rokne, J. An efficient algorithm for construction of the power diagram from the Voronoi diagram in the plane. International Journal of Computer Mathematics Vol. 61, Nos. 1–2, 49–61, 1996.
[60]
Karavelas, M. I.; Yvinec, M. Dynamic additively weighted Voronoi diagrams in 2D. In: Algorithms — ESA 2002. Lecture Notes in Computer Science, Vol. 2461. Möhring, R.; Raman, R. Eds. Springer Berlin Heidelberg, 586–598, 2002.
[61]
Karavelas, M. I.; Emiris, I. Z. Predicates for the planar additively weighted Voronoi diagram. Technical Report ECG-TR-122201-01. INRIA Sophia-Antipolis, 2002.
[62]
Wang, P. H.; Yuan, N.; Ma, Y. W.; Xin, S. Q.; He, Y.; Chen, S. M.; Xu, J.; Wang, W. Robust computation of 3D Apollonius diagrams. Computer Graphics Forum Vol. 39, No. 7, 43–55, 2020.
[63]
Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica Vol. 2, Nos. 1–4, 153–174, 1987.
[64]
Zhou, Q. N.; Jacobson, A. Thingi10K: A dataset of 10,000 3D-printing models. arXiv preprint arXiv:1605.04797, 2016.
[65]
Alt, H.; Godau, M. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications Vol. 5, Nos. 01n02, 75–91, 1995.
[66]
Rote, G. Computing the Fréchet distance between piecewise smooth curves. Computational Geometry Vol. 37, No. 3, 162–174, 2007.
[68]
Lo, S. H. A new mesh generation scheme for arbitrary planar domains. International Journal for Numerical Methods in Engineering Vol. 21, No. 8, 1403–1426, 1985.