Pankaj K. Agarwal, Jeff Phillips, and Bardia Sadri
Let M = (V, A) be a planar graph, let be a real parameter γ ≥ 0 and t: V -> R a height function. A γ-Lipschitz unimodel regression (γ-LUR) of t is a function s: V -> R such that s has a unique minimum, |s(u)-s(v)| ≤ γ for each {u,v} ∈ A, and |s-t|2 = ∑v ∈ V (s(v)-t(v))2 is minimized.
If M is a directed planar graph, then s is the γ-Lipschitz isotonic regression (γ-LIR) of t if s(u) ≤ s(v) ≤ s(u)+ γ for each (u,v) ∈ A and |s - t|2 is minimized. These problems arise in topological simplification of a height function. We present near-linear-time algorithms for LUR and LIR problems for two special cases: M is a path or a a tree.
Submitted [PDF]
Lipschitz Unimodal and Isotonic Regression on Paths and Trees
December 8, 2008