Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour

1. Montanari, U.: A note on minimal length polygonal approximation to a digitized contour. Communications of the ACM 13(1), 41–47 (1970)

   Article  MathSciNet  MATH  Google Scholar 

2. Sklansky, J., Chazin, R.L., Hansen, B.J.: Minimum perimeter polygons of digitized silhouettes. IEEE Trans. Computers 21(3), 260–268 (1972)

   Article  MathSciNet  MATH  Google Scholar 

3. Hobby, J.D.: Polygonal approximations that minimize the number of inflections. In: SODA 1993: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, pp. 93–102. Society for Industrial and Applied Mathematics, Philadelphia (1993)

   Google Scholar 

4. Klette, R., Yip, B.: The length of digital curves. Machine Graphics Vision 9(3), 673–703 (2000) (Also research report CITR-TR-54, University of Auckland, NZ. 1999)

   Google Scholar 

5. Coeurjolly, D., Klette, R.: A comparative evaluation of length estimators of digital curves. IEEE Trans. Pattern Analysis and Machine Intelligence 26(2), 252–258 (2004)

   Article  Google Scholar 

6. Klette, R., Rosenfeld, A.: Digital Geometry - Geometric Methods for Digital Picture Analysis. Morgan Kaufmann, San Francisco (2004)

   MATH  Google Scholar 

7. Sloboda, F., Stoer, J.: On piecewise linear approximation of planar Jordan curves. J. Comput. Appl. Math. 55(3), 369–383 (1994)

   Article  MathSciNet  MATH  Google Scholar 

8. Sloboda, F., Zat́ko, B.: On one-dimensional grid continua in R\(\hat{~}\)2. Technical report, Institute of Control Theory and Robotics, Slovak Academy of Sciences, Bratislava, Slovakia (1996)

   Google Scholar 

9. Sloboda, F., Zat́ko, B.: On approximation of jordan surfaces in 3D. In: Bertrand, G., Imiya, A., Klette, R. (eds.) Digital and Image Geometry. LNCS, vol. 2243, pp. 365–386. Springer, Heidelberg (2002)

   Chapter  Google Scholar 

10. Guibas, L.J., Hershberger, J.: Optimal shortest path queries in a simple polygon. In: SCG 1987: Proceedings of the third annual symposium on Computational geometry, pp. 50–63. ACM, New York (1987)

    Chapter  Google Scholar 

11. Klette, R., Kovalevsky, V., Yip, B.: On length estimation of digital curves. In: Vision geometry VIII, SPIE Proceedings, vol. 3811, pp. 117–128 (1999)

    Google Scholar 

12. Doerksen-Reiter, H., Debled-Rennesson, I.: Convex and concave parts of digital curves. In: Klette, R., Kozera, R., Noakes, L., Weickert, J. (eds.) Geometric Properties for Incomplete Data. Computational Imaging and Vision, vol. 31, pp. 145–160. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

13. Lachaud, J.O., Vialard, A., de Vieilleville, F.: Fast, accurate and convergent tangent estimation on digital contours. Image and Vision Computing 25(10), 1572–1587 (2007); Discrete Geometry for Computer Imagery 2005

    Article  Google Scholar 

14. Melkman, A.A.: On-line construction of the convex hull of a simple polyline. Inf. Process. Lett. 25(1), 11–12 (1987)

    Article  MathSciNet  MATH  Google Scholar 

15. Brlek, S., Lachaud, J.O., Provençal, X., Reutenauer, C.: Lyndon + christoffel = digitally convex. Pattern Recognition 42(10), 2239–2246 (2009); Selected papers from the 14th IAPR International Conference on Discrete Geometry for Computer Imagery 2008

    Article  MATH  Google Scholar 

16. Lothaire, M.: Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997)

    Book  MATH  Google Scholar 

17. Christoffel, E.B.: Observatio arithmetica. Annali di Mathematica 6, 145–152 (1875)

    Google Scholar 

18. Borel, J.P., Laubie, F.: Quelques mots sur la droite projective réelle. J. Théor. Nombres Bordeaux 5(1), 23–51 (1993)

    Article  Google Scholar 

19. Berstel, J., Lauve, A., Reutenauer, C., Saliola, F.V.: Combinatorics on words of CRM Monograph Series, vol. 27. American Mathematical Society, Providence (2009); Christoffel words and repetitions in words

    MATH  Google Scholar 

20. Duval, J.P.: Factorizing words over an ordered alphabet. J. Algorithms 4(4), 363–381 (1983)

    Article  MathSciNet  MATH  Google Scholar 

21. Fredricksen, H., Maiorana, J.: Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Math. 23(3), 207–210 (1978)

    Article  MathSciNet  MATH  Google Scholar 

22. Lothaire, M.: Applied combinatorics on words. Encyclopedia of Mathematics and its Applications, vol. 105. Cambridge University Press, Cambridge (2005)

    Book  MATH  Google Scholar 

23. Berstel, J., de Luca, A.: Sturmian words, Lyndon words and trees. Theoret. Comput. Sci. 178(1-2), 171–203 (1997)

    Article  MathSciNet  MATH  Google Scholar 

Download references