Representing a functional curve by curves with fewer peaks

We study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Let f be an input nonnegative piecewise linear functional curve of size n. We consider the following problems. (1) Uphill-downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing and one nonincreasing, such that their sum approximately represents f. (2) Unimodal representation (UR): Find a set of k nonnegative unimodal (single-peak) curves such that their sum approximately represents f. (3) Fewer-peak representation (FPR): Find a nonnegative piecewise linear curve with at most k peaks that approximately represents f. For each problem, we consider two versions. For UDPR, we study the feasibility version and the min-e version. For each of the UR and FPR problems, we study the min-k version and the min-e version. Little work has been done previously on these problems. We solve all problems (except the UR min-e) in optimal O(n) time, and the UR min-e version in O(n+mlogm) time, where m

Keywords:

• Discrete mathematics
• Combinatorics
• Algorithm design
• Piecewise linear function
• Mathematics
• curve approximation

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader