Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked curve y = φ(x) minimizing the L2 distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of single-peaked pieces under the condition that each single-peaked piece is within a fixed L2 distance from the corresponding portion of f.
|Title of host publication||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Editors||Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono|
|Number of pages||10|
|Publication status||Published - 2003|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|