Representing a Functional Curve by Curves with Fewer Peaks
In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f be an input piece-wise linear functional curve of size n. We consider several variations of the problems. (1) Uphill-downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given epsilon > 0, determine whether there is a feasible UDPR solution for f with an approximation error epsilon; its min-epsilon version: Compute the minimum approximation errror c* such that there is a feasible UDPR solution for f with error c*. For the UR problem, we study its min-k version: Given epsilon > 0, find a feasible solution with the minimum number k* of unimodal curves for f with an error epsilon; its min-epsilon version: given k > 0, compute the minimum error epsilon* such that there is a feasible solution with at most k unimodal curves for f with error epsilon*. For the FPR problem, we study its min-k version: Given epsilon > 0, find one feasible curve with the minimum number k* of peaks for f with an error epsilon; its min-epsilon version: given k >= 0, compute the minimum error epsilon* such that there is a feasible curve with at most k peaks for f with error epsilon*. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-epsilon version) in optimal O(n) time, and the UR min-epsilon version in O(n + m logm) time, where m < n is the number of peaks of f. Our algorithms are based on new geometric observations and interesting techniques.
curves with fewer peaks curve approximation curve simplification algorithm design