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 remaining points are regarded as outliers. We present an exact algorithm with O(k^{2}t^{4} + n^2\log n) runtime and O(kt^{2}) space, 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 area no more than the exact optimal value .
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}t^{4} + n^2\log n) runtime and O(kt^{2}) space, 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 .
R
remaining
uncovered
R
area no more than
at most
R
value
area