Fitting a Step Function to a Point Set
Fitting a Step Function to a Point Set
复制标题
将阶跃函数拟合到点集
DOI：
10.1007/s00453-009-9342-z
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
A. Vigneron
中科院分区：
文献类型：
--
作者：
Hervé Fournier;A. Vigneron
我们考虑将阶跃函数拟合到一组点的问题。更准确地说，给定一个整数k和一个平面上的n个点的集合P，我们的目标是找到一个具有k步的阶梯函数f，使f与P中所有点之间的最大垂直距离最小化。在P中的点按其x坐标排序的特殊情况下，我们给出了一个最优的Θ（n）时间算法。然后，我们展示了如何在时间O（nlog 4n）内解决这个问题的加权版本。最后，我们给出了一个O（nh2log n）算法的情况下，h离群值是允许的。所有算法的运行时间都与k无关。
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 4n). Finally, we give an O(nh2log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.