Algorithms for ordering unorganized points along parametrized curves. (English) Zbl 0789.65007

The aim of this study is to find an automatic method to order unorganized points which are uniformly distributed along curves. The authors present two practical algorithms based on geometrical criteria. The computational complexity of these algorithms is \(O(n\log n)\) and the space complexity \(O(n)\). Four consistent practical applications are discussed: feasibility of a piece machining, space object motion, algebraic curve plotting and sorting a restricted number of points non-uniformly distributed along an algebraic curve.
Reviewer: M.Gaşpar (Iaşi)


65D17 Computer-aided design (modeling of curves and surfaces)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65D10 Numerical smoothing, curve fitting
Full Text: DOI


[1] P. Alevizos, J.D. Boissonnat and M. Yvinec, Non-convex contour reconstruction, J. Symbolic Comp. 10 (1990) 225–252. · Zbl 0717.68098 · doi:10.1016/S0747-7171(08)80063-6
[2] C.L. Bajaj, C.M. Hoffmann, R.E. Lynch and J.E.M. Hopcroft, Tracing surface intersections, Comp. Aided Geom. Design 5 (1988) 285–307. · Zbl 0659.65012 · doi:10.1016/0167-8396(88)90010-6
[3] R.E. Barnhill, Surfaces in computer aided geometric design: A survey with new results, Comp. Aided Geom. Design 2 (1985) 1–17. · Zbl 0597.65001 · doi:10.1016/0167-8396(85)90002-0
[4] W. Böhm, G. Farin and J. Kahmann, A survey of curve and surface methods in CAGD, Comp. Aided Geom. Design 1 (1984) 1–60. · Zbl 0604.65005 · doi:10.1016/0167-8396(84)90003-7
[5] J.D. Boissonnat, Geometric structures for three-dimensional shape representation, ACM Trans. Graph. 3 (1984) 266–286. · doi:10.1145/357346.357349
[6] M.P. Do Carmo,Differential Geometry of Curves and Surfaces (Prentice-Hall, Englewood Cliffs, NJ, 1976).
[7] R.O. Duda and P.E. Hart,Pattern Classification and Scene Analysis (Wiley-Interscience, New York, 1973). · Zbl 0277.68056
[8] H. Edelsbrunner,Algorithms in Combinatorial Geometry (Springer, 1987). · Zbl 0634.52001
[9] Ch. Favardin, Détermination automatique de structures géométriques destinées à la reconstruction de courbes et de surfaces à partir de données ponctuelles, Thèse de Doctorat, Université Paul Sabatier de Toulouse III (1993).
[10] J.H. Friedman, F. Baskett and L.J. Shustek, An algorithm for finding nearest neighbours, IEEE Trans. Comp. (1975) 1000–1006. · Zbl 0311.68059
[11] J.H. Friedman, J.L. Bentley and R.A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Trans. Math. Software 3 (1977) 209–226. · Zbl 0364.68037 · doi:10.1145/355744.355745
[12] J.K. Johnstone and C.L. Bajaj, Sorting points along an algebraic curve, SIAM J. Comp. 19 (1990) 925–967. · Zbl 0711.68096 · doi:10.1137/0219065
[13] P. Krings, Fonctionnalité d’usinage sur le logiciel de CFAO Aérolis, Rapport de stage de fin d’études, AEROSPATIALE, Bureau détude de Toulouse-St. Martin, Département série service développement CAO (1991).
[14] P.J. Laurent, A. Le Méhauté and L.L. Schumaker,Proc. Int. Conf. on Curves and Surfaces, Chamonix (Academic Press, New York, 1991) pp. 135–138.
[15] J. O’Rourke, H. Booth and R. Washington, Connected-the-dots: A new heuristic, Comp. Vision, Graph. Image Proc. 39 (1987) 258–266. · Zbl 0657.68118 · doi:10.1016/S0734-189X(87)80169-X
[16] F.P. Preparata and M.I. Shamos,Computational Geometry; an Introduction (Springer, 1990). · Zbl 0575.68059
[17] J.J. Stoker,Pure and Applied Mathematics, Vol. 20,Differential Geometry (Wiley-Interscience, 1969). · Zbl 0182.54601
[18] W.N. Waggenspack, Jr. and C.C. Anderson, Piecewise parametric approximations for algebraic curves, Comp. Aided Geom. Design 6 (1989) 33–53. · Zbl 0661.65014 · doi:10.1016/0167-8396(89)90005-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.