On the approximation of curves by line segments using dynamic programming

By Richard Bellman. 1961

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering (2016, background): “This is a canonical instance of a sequence segmentation problem [3], which admits an O(|D S |×N) solution in our case.”
A dynamic programming segmentation procedure for hydrological and environmental time series (2006, methodology): “Dynamic programming has often been used in the past for the segmentation of curves (Bellman 1961) and waveforms (Jackson 2005; Kay 1998; Kay and Han, unpublished manuscript; Pavlidis and Horowitz 1974).”
1 Trend Filtering (2009, background): “In an early paper [5, 6], Bellman showed how DP can be used for segmented linear regression without the requirement of consistency at the join points.”
STUDIES IN ASTRONOMICAL TIME SERIES ANALYSIS. VI. BAYESIAN BLOCK REPRESENTATIONS (2012, background): “The details of this dynamic programming7 approach (Bellman 1961; Hubert et al. 2001; Dreyfus 2002) are in Jackson et al. (2005).”
A Dynamic Programming Algorithm for the Fused Lasso and L0-Segmentation (2013, methodology): “Timing comparisons with an alternative dynamic programming algorithm for the same task (Bellman 1961) show promising results.”
Mixed-integer nonlinear optimization*† (2013, background): “Bellman (1961) introduces a dynamic programming approach.”
Multiple Change-Point Estimation With a Total Variation Penalty (2010, methodology): “…Agence Nationale de la Recherche under grant ANR-06-BLAN-0078 KERNSIG. points K , the dynamic programming algorithm, proposed by Fisher (1958) and Bellman (1961), takes advantage of the intrinsic additive nature of the least-square objective to recursively compute the optimal change-points…”
Trajectory Data Mining (2015, methodology): “To ensure that the approximated trajectory is optimal, Bellman’s algorithm [7] employs a dynamic programming technique with a complexity of O(N(3)).”
Integrated Proteogenomic Characterization of Clear Cell Renal Cell Carcinoma (2019, methodology): “Alternative probabilistic algorithms were implemented in CNVEX, including algorithms based on recursive binary segmentation (RBS) (Gey and Lebarbier, 2008), and dynamic programming (Bellman, 1961), as implemented in the R-package jointseg (Pierre-Jean et al., 2015).”
An algorithm for optimal partitioning of data on an interval (2003, background): “The dynamic programming idea for this kind of problem seems to have originated with Bellman [6]: a paper which influenced Kay’s work [12]–[14].”
Homogeneity and change-point detection tests for multivariate data using rank statistics (2011, methodology): “We refer here to the classical dynamic programming approach to the segmentation task which is described in Kay (1993) used by, among others, Bai and Perron (2003) and can be traced back to the note by Bellman (1961).”
Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions (2014, background): “The above problem is a result of the so-called ‘curse of dimensionality’, where the search space grows exponentially with the growth in decision space dimension (Bellman, 1961), i.”