Open Access System for Information Sharing

Login Library

 

Article
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Square and Rectangle Covering with Outliers

Title
Square and Rectangle Covering with Outliers
Authors
Ahn H.-KBae,, Sang WonKim, Sang-SubKorman, MatiasReinbacher, IrisWanbin Son
POSTECH Authors
Ahn H.-K
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
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.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

안희갑AHN, HEE-KAP
Grad. School of AI
Read more

Views & Downloads

Browse