@inbook{a649859f23eb4630b2bd99e287c86bcc,

title = "Linear time algorithm for approximating a curve by a single-peaked curve",

abstract = "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.",

author = "Jinhee Chun and Kunihiko Sadakane and Takeshi Tokuyama",

year = "2003",

doi = "10.1007/978-3-540-24587-2_3",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "6--15",

editor = "Toshihide Ibaraki and Naoki Katoh and Hirotaka Ono",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}