论文标题
与离群值的最小封闭平行四边形
Minimum Enclosing Parallelogram with Outliers
论文作者
论文摘要
我们研究了与离群值最小包裹矩形的问题，该问题要求找到给定的$ n $ planar点，这是一个最低面积的矩形，该矩形至少包含$（n-t）$点。被发现的观点被视为离群值。假设没有三个点位于同一条线上，我们会以$ o（kt^3+ktn+n^2 \ log n）$ O（kt^3+ktn+n^2 \ log n）呈现精确算法。这里$ k $表示第一个$（t+1）$凸面上的点数。我们进一步提出了一种使用运行时$ O（n+\ mbox {poly}（\ log {n}，t，1/ε））$的采样算法，其高概率很高，可找到一个至少覆盖$（1-ε）（n-t）$的矩形。
We study the problem of minimum enclosing rectangle with outliers, which asks to find, for a given set of $n$ planar points, a rectangle with minimum area that encloses at least $(n-t)$ points. The uncovered points are regarded as outliers. We present an exact algorithm with $O(kt^3+ktn+n^2\log n)$ runtime, assuming that no three points lie on the same line. Here $k$ denotes the number of points on the first $(t+1)$ convex layers. We further propose a sampling algorithm with runtime $O(n+\mbox{poly}(\log{n}, t, 1/ε))$, which with high probability finds a rectangle covering at least $(1-ε)(n-t)$ points with at most the exact optimal area.
