Best piecewise constant approximation of a function of single variable (Q1111948): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q61688029, #quickstatements; #temporary_batch_1707252663060 |
Removed claim: reviewed by (P1447): Item:Q178348 |
||
Property / reviewed by | |||
Property / reviewed by: Andrzej Nowak / rank | |||
Revision as of 08:15, 10 February 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