Covering Points by Disjoint Boxes with Outliers

Details Covering Points by Disjoint Boxes with Outliers Covering Points by Disjoint Boxes with Outliers

2009-10-09

arxiv.org/abs/0910.1643v2

Computer Science

Computational Geometry

updated version: - changed problem from 'cover exactly n-k points' to 'cover at least n-k points' to avoid having non-feasible

Scientific paper

For a set of n points in the plane, we consider the axis--aligned (p,k)-Box Covering problem: Find p axis-aligned, pairwise-disjoint boxes that together contain n-k points. In this paper, we consider the boxes to be either squares or rectangles, and we want to minimize the area of the largest box. For general p we show that the problem is NP-hard for both squares and rectangles. For a small, fixed number p, we give algorithms that find the solution in the following running times: For squares we have O(n+k log k) time for p=1, and O(n log n+k^p log^p k time for p = 2,3. For rectangles we get O(n + k^3) for p = 1 and O(n log n+k^{2+p} log^{p-1} k) time for p = 2,3. In all cases, our algorithms use O(n) space.

Affiliated with

Also associated with

No associations

Rating

Covering Points by Disjoint Boxes with Outliers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering Points by Disjoint Boxes with Outliers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering Points by Disjoint Boxes with Outliers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-50660