Improvement of the Shortest Path Problem with Geodesic-Like Method

Authors: Wen-Haw Chen

Abstract:

This paper proposes a method to improve the shortest path problem on a NURBS (Non-uniform rational basis spline) surfaces. It comes from an application of the theory in classic differential geometry on surfaces and can improve the distance problem not only on surfaces but in the Euclidean 3-space R3 .

Keywords: shortest paths, geodesic-like method, NURBS surfaces.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329725

References:

[1] M. P. do Carmo, Differential Geometry of Curves and Surfaces, Prentice- Hall, Englewood Cliffs, NJ. (1976).
[2] V. Caselles, R. Kimmel and G. Sapiro, Geodesic active contours, Int. J. Comput. Vision 22 (1) (1997) 61-71.
[3] X. D. Chen, H. Su, J. H. Yong, J. C. Paul and J. G. Sun, A counterexample on point inversion and projection for NURBS curve, CAGD 24 (2007) 302.
[4] X.-D. Chen, J.-H. Yong, Guozhao Wang, J.-C. Paul and Gang Xu, Computing the minimum distance between a point and a NURBS curve, CAD 40 (2008) 1051-1054.
[5] X.-D. Chena, J.-H. Yonga, G.-Q. Zhenga, J.-C. Paula and J.-G. Suna, Computing minimum distance between two implicit algebraic surfaces, CAD 38 (2006) 1053-1061.
[6] S.-G. Chen, Geodesic-like curves on parametric surfaces, CAGD 27 (2010) 106-117.
[7] S.-G. Chen and W.-H. Chen, Computation of Shortest Paths Between Two Curves on Surfaces by Geodesic-Like Algorithm, preprint.
[8] J. M. Gutierrez and M. A. Hernandez, An acceleration of Newton-s method: Super- Halley method, Applied Mathematics and Computation 117(2) (2001) 223-239.
[9] I. Hotz and H. Hagen, Visualizing geodesics, In: Proceedings IEEE Visualization (Salt Lake City, UT,2000) pp. 311-318.
[10] S. M. Hu and J. Wallner, A second order algorithm for orthogonal projection onto curves and surfaces, CAGD 22(3) (2005) 251-60.
[11] T. Kanai and H. Suzuki, Approxmiate shortest path on a polyhedral surface and its applications, CAD 33 (2001) 801-811
[12] E. Kasap, M. Yapici and F. T. Akyildiz, A numerical study for computation of geodesic curves, Applied Mathematics and Computation 171(2) (2005) 1206-1213.
[13] K.-J. Kim, Minimum distance between a canal surface and a simple surface, CAD 35 (2003) 871-879.
[14] R. Kimmel, Intrinsic scale space for images on surfaces: the geodesic curvature flow, Graph. Models Image Process 59(5) (1997) 365-372.
[15] D. Martinez, L. Velho and P. C. Carvalho, Computing geodesics on triangular meshes, Computer & Graphics 29 (2005) 667-675.
[16] Y. L. Ma and W. T. Hewitt, Point inversion and projection for NURBS curve and surface: Control polygon approach, CAGD 20(2) (2003) 79-99.
[17] T. Maekawa, Computation of shortest path on free-form parametric surfaces, Journal of Mechanical Design, Transactions of ASME, 118(4) (1996) 499-508.
[18] N. Patrikalakis, T. Maekawa, Shape interrogation for computer aided design and manufacturing, Springer; 2001.
[19] L. Piegl and W. Tiller, Parametrization for surface fitting in reverse engineering, CAD 33(8) (2001) 593-603.
[20] J. Pegna and F. E. Wolter, Surface curve design by orthogonal projection of space curves onto free-form surfaces, Journal of Mechanical Design, ASME Transactions 118(1) (1996) 45-52.
[21] E. Polak, Optimization, algorithms and consistent approximations, Berlin (Heidelberg, NY): Springer-Verlag; 1997.
[22] K. Polthier, M. Schmies, 1998. In: Hege, H.C., Polthier, H.K. (Eds.), Straightest Geodesics On Polyhedral Surfaces in Mathematical Visualization, Springer-Verlag, Berlin.
[23] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C: The art of scientific computing, 2nd ed.NewYork: Cambridge University Press, 1992.
[24] G. V. V. Ravi Kumar, Prabha Srinivasan, V. Devaraja Holla, K. G. Shastry and B. G. Prakash, Geodesic curve computations on surfaces, CAGD 20(2) (2003) 119-133.
[25] J. S'anchez-Reyesa and R. Doradob, Constrained design of polynomial surfaces from geodesic curves, CAD 40 (2008) 49-55.
[26] I. Selimovic, Improved algorithms for the projection of points on NURBS curves and surfaces, CAGD 23(5) (2006) 439-445.
[27] V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler, H. Hoppe, Fast exact and approximate geodesics on meshes, ACM Transactions on Graphics (Proc. of SIGGRAPH 2005), 24(3), 553-560.
[28] Y. Ye, Combining binary search and Newton-s method to compute real roots for a class of real functions, Journal of Complexity 10(3) (1994) 271-280.