Fitting a step function to a point set

Hervé Fournier*, Antoine Vigneron

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 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 Θ(n logn) 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(n log4 n). Finally, we give an O(n h 2 logh) algorithm for the case where h outliers are allowed, and the input is sorted. The running time of all our algorithms is independent of k.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540877436, 9783540877431
StatePublished - 2008
Event16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany
Duration: Sep 15 2008Sep 17 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5193 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th Annual European Symposium on Algorithms, ESA 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this