Square and rectangle covering with outliers

Hee Kap Ahn, Sang Won Bae, Sang Sub Kim, Matias Korman, Iris Reinbacher, Wanbin Son

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings
Number of pages9
Publication statusPublished - 2009
Externally publishedYes
Event3rd International Frontiers of Algorithmics Workshop, FAW 2009 - Hefei, China
Duration: 2009 Jun 202009 Jun 23

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5598 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Frontiers of Algorithmics Workshop, FAW 2009

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Square and rectangle covering with outliers'. Together they form a unique fingerprint.

Cite this