Forma, Vol. 10 (No. 2), pp. 133-144, 1995
Original Paper

Optimal Approximation of a Curve by a Polygonal Chain with Vertices on a Grid

Tetsuo Asano1, Naoki Katoh2, Elena Lodi3 and Thomas Roos4

1Department of Engineering Informatics, Osaka Electro-Communication University, Hatsu-cho, Neyagawa 572, Japan
2Kobe University of Commerce, Nishi-ku, Kobe 651-21, Japan
3Department of Mathematics, University of Siena, 53100 Siena, Italy
4Theoretische Informatik, ETH Zentrum, CH-8092 Z"urich, Switzerland

(Received April 17, 1995; Accepted August 31, 1995)

Keywords: Algorithm, Approximation of a Curve, Computational Geometry, Dynamic Programming, Minimum-Weight Path

Abstract. This paper presents efficient algorithms for approximating a curve by a polygonal chain with vertices on a grid. We are given an x-monotone curve y = f(x) consisting of N pieces on some m n grid. Our goal is to compute an approximation of the given curve by an x-monotone polygonal chain whose vertices are points of the grid. For that, we discuss several optimization criteria such as minimizing the area of the region bounded by the given curve and the polygonal chain. Our approach is based on a reduction to the computation of minimum-cost paths. We present an O(N + n2) time and O(N + n) space algorithm for computing an optimal x-monotone polygonal chain. If we add the restriction that the horizontal lengths of the line segments used for the approximation is bounded by k, the time complexity can further be reduced to O(N + kn). In both cases, the time complexity does not depend on the range m of the function. Applications of this problem can be found, e.g., in the area of computer graphics.