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

Tetsuo Asano¹, Naoki Katoh², Elena Lodi³ and Thomas Roos⁴

¹Department of Engineering Informatics, Osaka Electro-Communication University, Hatsu-cho, Neyagawa 572, Japan
²Kobe University of Commerce, Nishi-ku, Kobe 651-21, Japan
³Department of Mathematics, University of Siena, 53100 Siena, Italy
⁴Theoretische 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 + n²) 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.