Minimum Enclosing Parallelogram with Outliers

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(k{t}^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+poly(\log n,t,1\mathrm{/}ϵ))$, which with high probability finds a rectangle covering at least $(1-ϵ)(n-t)$ points with at most the exact optimal area.