多邊形估計[1]是指找到一條多邊形曲線P'，使得P'最近似於多邊形曲線P，亦即P'與P的誤差值E為最小，且P'的點集合是P的點集合中的一個子集合，通常分成以下兩類：第一，給定一個誤差值門檻，希望找到一條具有最少線段數的多邊形P'，且P'與P的誤差值E小於門檻值。第二，給定一個固定線段數M，希望找到一條具有M個線段的多邊形P'，使得P'與P具有最小的誤差值E。已經有許多的學者針對這兩類的問題，提出很有效的演算法來加以解決，然而這些演算法都被限制在開放式的多邊形，對於封閉式的多邊形，卻一直沒有一個很有效率的方式去近似估計，本篇論文便是針對封閉式的多邊形，利用一些簡單的圖形分析得知覆蓋某一點的所有線段中，必定會有一條屬於最佳近似多邊形的情形，提出一個有效率的方法，可以降低傳統方法的複雜度。實驗的結果也證明了，在封閉式多邊形近似估計的問題上，本篇論文的演算法相對於傳統演算法，平均可以減少97.4%的執行時間。

Given a polygonal curve P with n vertices, the closed polygonal
approximation problem is defined to find a closed polygon P' to
approximate P with minimal polygonal segments under a given
tolerant error. This paper presents an O(En^2)-time
algorithm for solving the closed polygonal approximation problem
where E denotes the minimum of covering edge numbers for all
vertices. Since it's almost always that E<<n, the proposed
algorithm is much faster than the previous algorithm, which takes
O(n^3) time, for solving the same problem. Based on several real
closed curves, experimental results indicate that our proposed
algorithm can reduce the overhead of executive time in the previous
algorithm up to 97.4% for solving the closed polygonal
approximation problem.

[1] R.C. Gonzalez, R.E. Woods, Digital Image Processing, Section 8.1.2: Polygonal Approximations, Addison-Wesley, New York, 1992.
[2] B.K. Natarajan. On comparing and compressing piecewise linear curves. Technical Report, Hewlett Packard, 1991.
[3] B.K. Natarajan. And J.Ruppert. On sparse approximations of curves and functions. Proc. 4th Canadian Conference on Computational Geometry, pages 250-256, 1992.
[4] C.L.B Jordan, T. Ebrahimi, M. Kunt, Progressive content-based shape compression for retrieval of binary images, Comput. Vision Image Understanding 71 (2) 198-212 1998.
[5] P.L. Rosin, Techniques for assessing polygonal approximations of curves, IEEE Trans. Pattern Analysis Machine Intelligence 19 (6) 659-666 1997.
[6] Y. Sato, Piecewise linear approximation of plane curves by perimeter optimization, Pattern Recognition 25 (12) 1535–1543 1992.
[7] A. Pikaz, I. Dinstein, Optimal polygonal approximation of digital curves, Pattern Recognition 28 (3) 373-379 1995.
[8] Y.M. Sharaiha, N. Christofides, An optimal algorithm for the straight segment approximation of digital arcs, CVGIP: Graphical Models Image Process. 55 (5) 397-407 1993.
[9] J.G. Dunham, Optimization piecewise linear approximation of planar curves, IEEE Trans. Pattern Analysis Machine Intelligence 8 (1) 67-75 1986.
[10] H. Imai, M. Iri, Computational-geometric methods for polygonal approximations of a curve, Computer Vision Graphics Image Process. 36 31-41 1986.
[11] A. Melkman, J. O’Rourke, On polygonal chain approximation, in: G.T. Toussaint (Ed.), Computational Morphology, North-Holland, Amsterdam, pp. 87–95 , 1988.
[12] W.S. Chan, F. Chin, Approximation of polygonal curves with minimum number of line segments or minimum error, Int. J. Computer Geometric Application 6 59–77 1996.
[13] D.Z. Chen, O. Daescu, Space-efficient algorithms for approximating polygonal curves in two dimensional space, in: W.L. Hsu, M.Y. Kao (Eds.), The Fourth Annual International Conference COCOON’98, pp. 45–54, 1998.
[14] G. Barequet, D.Z. Chen, O. Daescu, M.T. Goodrich, J. Snoeyink, Efficiently approximating polygonal paths in three and higher dimensions, Proceedings of the 14th Annual ACM Symposium on Computational Geometry, pp. 317–326, 1998.
[15] S.L. Hakimi, E.F. Schmeichel, Fitting polygonal functions to a set of points in the plane, CVGIP: Graphic Models Image Process. 53 (2) 132–136 1991.
[16] D. Eu, G.T. Toussaint, On approximating polygonal curves in two and three dimensions, CVGIP: Graphic Models Image Process. 56 (3) 231–246 1994.
[17] H. Imai, M. Iri, Polygonal approximations of a curve—formulations and algorithms, in: G.T. Toussaint (Ed.), Computational Morphology, North-Holland, Amsterdam, pp. 71–86, 1988.
[18] Alexander Kolesnikov, Pasi Fr&auml;nti, Polygonal Approximation of Closed Contours, SCIA : 778-785 2003.
[19] Yin, P.-Y., Anew method for polygonal approximation using genetic algorithms. Pattern Recognition Letter 19, 1017-1026, 1998,
[20] Huang, S.-C., Sun, Y.-N., Polygonal approximation using genetic algorithms. Pattern Recognition 32, 1409-1420, 1999.
[21] J.C. Perez, E. Vidal, Optimum polygonal approximation of digitized curves, Pattern Recognition Letter 15 743–750 1994.
[22] B.K. Ray, K.S. Ray, A non-parametric sequential method for polygonal approximation of digital curves, Pattern Recognition Letter 15 161–167 1994.
[23] K.L. Chung, W.M. Yan, and W.Y. Chen, Efficient algorithms for 3-D polygonal approximation based on LISE criterion, Pattern Recognition, 35(11), pp. 2539-2548, 2002.
[24] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, Section 25.2, Dijkstra’s Algorithm, The MIT Press, Cambridge, MA, 1990.