2009/12/28 by Pankaj K. Agarwal, Agarwal, Pankaj K., Jeff M. Phillips +3
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Data Visualization and Analytics #Digital Image Processing Techniques #FOS: Computer and information sciences #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.0912.5182
openalex publication_date 2009/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe algorithms for finding the regression of t, a sequence of values, to the closest sequence s by mean squared error, so that s is always increasing (isotonicity) and so the values of two consecutive points do not increase by too much (Lipschitz). The isotonicity constraint can be replaced with a unimodular constraint, where there is exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each scenario we describe near-linear time algorithms.