TY - GEN
T1 - Square and rectangle covering with outliers
AU - Ahn, Hee Kap
AU - Bae, Sang Won
AU - Kim, Sang Sub
AU - Korman, Matias
AU - Reinbacher, Iris
AU - Son, Wanbin
PY - 2009
Y1 - 2009
N2 - 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 exactly n-k points. Here, our boxes are either squares or rectangles, and we want to minimize the area of the largest box. For squares, we present algorithms that find the solution in O(n+klogk) time for p=1, and in O(nlogn+k p log p k) time for p=2,3. For rectangles we have running times of O(n+k 3) for p=1 and O(nlogn+k 2+p log p-1 k) time for p=2,3. In all cases, our algorithms use O(n) space.
AB - 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 exactly n-k points. Here, our boxes are either squares or rectangles, and we want to minimize the area of the largest box. For squares, we present algorithms that find the solution in O(n+klogk) time for p=1, and in O(nlogn+k p log p k) time for p=2,3. For rectangles we have running times of O(n+k 3) for p=1 and O(nlogn+k 2+p log p-1 k) time for p=2,3. In all cases, our algorithms use O(n) space.
UR - http://www.scopus.com/inward/record.url?scp=71049150864&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=71049150864&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02270-8_15
DO - 10.1007/978-3-642-02270-8_15
M3 - Conference contribution
AN - SCOPUS:71049150864
SN - 3642022693
SN - 9783642022692
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 132
EP - 140
BT - Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings
T2 - 3rd International Frontiers of Algorithmics Workshop, FAW 2009
Y2 - 20 June 2009 through 23 June 2009
ER -