Approximating Points by a Piecewise Linear Function

Approximating points by piecewise linear functions is an intensively researched topic in computational geometry. In this paper, we study, based on the uniform error metric, an array of variations of this problem in 2‐D and 3‐D, including points with weights, approximation with violations, using step functions or more generally piecewise linear functions. We consider both the min‐# (i.e., given an error tolerance ϵ, minimizing the size k of the approximating function) and min‐ϵ (i.e., given a size k of the approximating function, minimizing the error tolerance ϵ) versions of the problems. Our algorithms either improve on the previously best‐known solutions or are the first known results for the respective problems. Our approaches are based on interesting geometric observations and algorithmic techniques. Some data structures we develop are of independent interest and may find other applications.