APPROXIMATING POLYGONAL CURVES IN 2 AND 3 DIMENSIONS

We discuss the weighted minimum number polygonal approximation problem . Eu and Toussaint (1994, CVGIP: Graphical Models Image Process. 56, 2 31-246) considered this problem subject to the parallel-strip error cr iterion in R-2 with L-q distance metrics, and they concluded that it c an be solved in O (n(2)) time by using the Cone intersection method. I n this note, we clarify part of their discussion and show that solving their problem correctly requires O (n(2) log n) time. Also, we discus s the weighted minimum number problem subject to the line segment erro r criterion. When input curves are strictly monotone in R-3, We demons trate that if the L-1 or L-infinity metric is used, this problem also can be solved in O(n(2)) time. (C) 1998 Academic Press.