| Optimal Approximation of Monotone Curves on a Grid (Extended Abstract) (2007) | |||||||||||||||
Abstract | |||||||||||||||
| ) Tetsuo Asano 1 Naoki Katoh 2 Elena Lodi 3 Thomas Roos 4 1 Dept. of Applied Electronics, Osaka Electro-Communication Univ., Neyagawa, Osaka 572, Japan (asano@djinni.osakac.ac.jp) 2 Kobe University of Commerce, Kobe, Japan (naoki@kobeuc.ac.jp) 3 University of Siena, Siena, Italy (lodi@di.unipi.it) 4 Theoretische Informatik, ETH Zentrum, CH-8092 Zurich, Switzerland (roos@inf.ethz.ch; Fax: +41 1 632 1172) 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 \Theta 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... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||