Fitting a step function to a point set

Hervé Fournier, Antoine Vigneron*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 2log∈n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.

Original languageEnglish (US)
Pages (from-to)95-109
Number of pages15
JournalAlgorithmica (New York)
Issue number1
StatePublished - May 2011


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

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Fitting a step function to a point set'. Together they form a unique fingerprint.

Cite this