Best piecewise constant approximation of a function of single variable
type: Item
instance of: scholarly article
title: Best piecewise constant approximation of a function of single variable
zbMATH Open document ID: 0658.90095
DOI: 10.1016/0167-6377(88)90030-2
author: Hiroshi Konno
author: Takahito Kuno
published in: Operations Research Letters
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 41A30
zbMATH DE Number: 4076994
zbMATH Keywords: piecewise constant functions
zbMATH Keywords: shortest path
zbMATH Keywords: polynomial time algorithms
Wikidata QID: Q61688029
reviewed by: Andrzej Nowak
MaRDI profile type: Publication
full work available at URL: 0167-6377(88)90030-2
OpenAlex ID: W2077389338
cites work: On the approximation of curves by line segments using dynamic programming
cites work: Two Algorithms for Piecewise-Linear Continuous Approximation of Functions of One Variable
description: scientific article; zbMATH DE number 4076994