Fitting a step function to a point set

Hervé Fournier; Antoine Vigneron

doi:10.1007/978-3-540-87744-8_37

Fitting a step function to a point set

Hervé Fournier^*, Antoine Vigneron

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

15 Scopus citations

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 Θ(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 log⁴ n). Finally, we give an O(n h ² 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 language	English (US)
Title of host publication	Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Publisher	Springer Verlag
Pages	442-453
Number of pages	12
ISBN (Print)	3540877436, 9783540877431
DOIs	https://doi.org/10.1007/978-3-540-87744-8_37
State	Published - 2008
Externally published	Yes
Event	16th Annual European Symposium on Algorithms, ESA 2008 - Karlsruhe, Germany Duration: Sep 15 2008 → Sep 17 2008

Publication series

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

Other

Other	16th Annual European Symposium on Algorithms, ESA 2008
Country/Territory	Germany
City	Karlsruhe
Period	09/15/08 → 09/17/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Fournier, H., & Vigneron, A. (2008). Fitting a step function to a point set. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings (pp. 442-453). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-87744-8_37

@inproceedings{8d05dd2c81c24bc2bb3ff0611e189488,

title = "Fitting a step function to a point set",

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 Θ(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.",

author = "Herv{\'e} Fournier and Antoine Vigneron",

year = "2008",

doi = "10.1007/978-3-540-87744-8_37",

language = "English (US)",

isbn = "3540877436",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "442--453",

booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",

address = "Germany",

note = "16th Annual European Symposium on Algorithms, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",

}

Fournier, H & Vigneron, A 2008, Fitting a step function to a point set. in Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS, Springer Verlag, pp. 442-453, 16th Annual European Symposium on Algorithms, ESA 2008, Karlsruhe, Germany, 09/15/08. https://doi.org/10.1007/978-3-540-87744-8_37

Fitting a step function to a point set. / Fournier, Hervé; Vigneron, Antoine.
Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Springer Verlag, 2008. p. 442-453 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Fitting a step function to a point set

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this