Square and Rectangle Covering with Outliers
SCIE
SCOPUS
- Title
- Square and Rectangle Covering with Outliers
- Authors
- Ahn H.-K; Bae,, Sang Won; Kim, Sang-Sub; Korman, Matias; Reinbacher, Iris; Wanbin Son
- Date Issued
- 2009-06
- Publisher
- SPRINGER
- Abstract
- 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 + k log k) time for p = 1. and in O(n log n + 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(n log n + k(2+p) log(p-1) k) time for p = 2; 3. In all cases; our algorithms use O(n) space.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/35946
- DOI
- 10.1007/978-3-642-02270-8_15
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- LECTURE NOTES IN COMPUTER SCIENCE, vol. 5598, page. 132 - 140, 2009-06
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.