Best piecewise constant approximation of a function of single variable (Q1111948): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Best piecewise constant approximation of a function of single variable |
scientific article |
Statements
Best piecewise constant approximation of a function of single variable (English)
0 references
1988
0 references
Let F(I) be a class of piecewise constant functions on an interval I. The following two problems are studied: (1) Given \(f\in F(I)\) and a positive constant \(\epsilon\), find \(g\in F(I)\) such that \(\| g-f\| \leq \epsilon\) and g has a minimal number of constant pieces. (2) Given \(f\in F(I)\) and a positive integer k, find \(g\in F(I)\) which minimizes \(\| g-f\|\) among all functions with the number of constant pieces less then k. These problems are solved by using shortest path and dynamic programming techniques, and polynomial time algorithms are proposed. Some applications are briefly described.
0 references
piecewise constant functions
0 references
shortest path
0 references
polynomial time algorithms
0 references