TY - GEN

T1 - Fitting a step function to a point set

AU - Fournier, Hervé

AU - Vigneron, Antoine

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=57749183176&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-87744-8_37

DO - 10.1007/978-3-540-87744-8_37

M3 - Conference contribution

AN - SCOPUS:57749183176

SN - 3540877436

SN - 9783540877431

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 442

EP - 453

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 16th Annual European Symposium on Algorithms, ESA 2008

Y2 - 15 September 2008 through 17 September 2008

ER -