Linear-time fitting of a \(k\)-step function

DOI10.1016/j.dam.2017.11.005zbMath1437.68183OpenAlexW2773532448MaRDI QIDQ2181242

Binay K. Bhattacharya, Sandip Das, Tsunehiko Kameda

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.11.005

zbMATH Keywords

facility locationoptimal algorithmprune-and-searchminmax error histogramstep-function fitting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items

The weighted \(k\)-center problem in trees for fixed \(k\)

Cites Work

• Unnamed Item
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Fitting a step function to a point set
• Time bounds for selection
• A deterministic algorithm for fitting a step function to a weighted point-set
• A new algorithm for fitting a rectilinear x-monotone curve to a set of points in the plane
• A Randomized Algorithm for Weighted Approximation of Points by a Step Function
• Generalized Selection and Ranking: Sorted Matrices
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• Approximating Points by a Piecewise Linear Function: I
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Weighted Rectilinear Approximation of Points in the Plane
• Fitting rectilinear polgonal curves to a set of points in the plane.