  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/\epsilon))$, which with
high probability finds a rectangle covering at least $(1-\epsilon)(n-t)$ points
with at most the exact optimal area.
