Fitting a Step Function to a Point Set

Hervé Fournier (1, 2) , Antoine Vigneron (3)

1 UVSQ - Université de Versailles Saint-Quentin-en-Yvelines
2 SMIS - Secured and Mobile Information Systems
3 MIA-JOUY - Unité de biométrie et intelligence artificielle de Jouy

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.

Mots clés: algoritms

Mots clés: plane; approximation; fonction

Domaines: Mathématiques [math]; Informatique [cs]

Hervé Fournier, Antoine Vigneron. Fitting a Step Function to a Point Set. 16th Annual European Symposium on Algorithms, Sep 2008, Karlsruhe, Germany. ⟨10.1007/978-3-540-87744-8_37⟩. ⟨hal-02750559⟩