Covering points by disjoint boxes with outliers
SCIE
SCOPUS
- Title
- Covering points by disjoint boxes with outliers
- Authors
- Ahn, HK; Sang Won Bae; Erik D. Demaine; Martin L. Demaine; Sang-Sub Kim; Matias Korman; Iris Reinbacher; Wanbin Son
- Date Issued
- 2011-04
- Publisher
- Elsevier
- 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 at least 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.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/16991
- DOI
- 10.1016/j.comgeo.2010.10.002
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 44, no. 3, page. 178 - 190, 2011-04
- 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.