## Abstract

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog∈n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog∈ ^{4} n). Finally, we give an O(nh ^{2}log∈n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.

Original language | English (US) |
---|---|

Pages (from-to) | 95-109 |

Number of pages | 15 |

Journal | Algorithmica (New York) |

Volume | 60 |

Issue number | 1 |

DOIs | |

State | Published - May 2011 |

## Keywords

- Algorithm Design
- Computational geometry
- Histogram
- Optimization
- Shape fitting

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics