Linear-time fitting of a k-step function

DOI10.1007/978-3-319-29221-2_8MaRDI QIDQ2795937zbMATH OpenOpenAlexFDO

Authors Binay Bhattacharya, Sandip Das, Tsunehiko Kameda

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07537

zbMATH Keywords

anchored step functionlinear-time algorithmprune-and-searchstep-function fittingweighted points

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: Given a set of $n$ weighted points on the $x$-$y$ plane, we want to find a step function consisting of $k$ horizontal steps such that the maximum vertical weighted distance from any point to a step is minimized. We solve this problem in $O(n)$ time when $k$ is a constant. Our approach relies on the prune-and-search technique, and can be adapted to design similar linear time algorithms to solve the line-constrained k-center problem and the size-$k$ histogram construction problem as well.

Recommendations

• Linear-time fitting of a \(k\)-step function
• A deterministic algorithm for fitting a step function to a weighted point-set
• Fitting a step function to a point set
• Fitting a Step Function to a Point Set
• A randomized algorithm for weighted approximation of points by a step function

Cites work

• 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
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximating points by a piecewise linear function: I
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Fitting a step function to a point set
• Fitting rectilinear polgonal curves to a set of points in the plane.
• Generalized Selection and Ranking: Sorted Matrices
• scientific article; zbMATH DE number 432817 (Why is no real title available?)
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• Optimal Algorithms for the Weighted p-Center Problems on the Real Line for Small p
• Slowing down sorting networks to obtain faster sorting algorithms
• Some variations on constrained minimum enclosing circle problem
• Sorting in Average Time o(\log \,n)
• Weighted Rectilinear Approximation of Points in the Plane

Cited in

(4)

• A deterministic algorithm for fitting a step function to a weighted point-set
• Linear-time fitting of a \(k\)-step function
• Fitting a Step Function to a Point Set
• Fitting a step function to a point set

This page was built for publication: Linear-time fitting of a \(k\)-step function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795937)