We study the problem of minimum enclosing parallelogram with outliers, which asks to find, for a given set of n planar points, a parallelogram with minimum area that encloses at least (n-t) points , where the uncovered points are regarded as outliers. We present an exact algorithm with O( k^{2 +  n^2\log n) runtime and O(kt^{2 , assuming that no three points lie on the same line. Here k =k(n,t) denotes the number of points on the first (t+1) convex layers. We further propose an sampling algorithm with runtime O(n+poly(n, t, 1/\epsilon)), which with high probability finds a parallelogram covering at least (1-\epsilon)(n-t ) and at most (n-t+1 ) points with at most the exact optimal area.
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 + kt^2\log{n 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(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.
R
parallelogram
rectangle
R
parallelogram
rectangle
R
, where the
. The
R
k^{2
kt^3
A
kt^2\log{n
D
and O(kt^{2
D
=k(n,t)
R
an
a
R
parallelogram
rectangle
D
) and at most (n-t+1