  Given n data points in R^d, an appropriate edge-weighted graph connecting the
data points finds application in solving clustering, classification, and
regresssion problems. The graph proposed by Daitch, Kelner and Spielman
(ICML~2009) can be computed by quadratic programming and hence in polynomial
time. While a more efficient algorithm would be preferable, replacing quadratic
programming is challenging even for the special case of points in one
dimension. We develop a dynamic programming algorithm for this case that runs
in O(n^2) time.
