Computing Least Median of Squares Regression Lines and Guided Topological Sweep
提出一种O(n²)时间、O(n)空间的算法，用于计算数据点的最小中位数平方回归直线，改进了此前问题的上界，该算法基于线排列的拓扑扫描方法。
Abstract Given a set of data points pi = (xi, yi ) for 1 ≤ i ≤ n, the least median of squares regression line is a line y = ax + b for which the median of the squared residuals is a minimum over all choices of a and b. An algorithm is described that computes such a line in O(n 2) time and O(n) memory space, thus improving previous upper bounds on the problem. This algorithm is an application of a general method built on top of the topological sweep of line arrangements. Key Words: Computational geometryDualityLine arrangementsRobust statistics