Covering many points with a small-area box

Mark T. de Berg, Sergio Cabello, Otfried Cheong, David Eppstein, Christian Knauer

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
25 Downloads (Pure)


Let P be a set of n points in the plane. We show how to find, for a given integer k >0, the smallest-area axis-parallel rectangle that covers k points of P in O(nk2logn+ n log2 n) time. We also consider the problem of, given a value α > 0, covering as many points of P as possible with an axis-parallel rectangle of area at most α. For this problem we give a probabilistic (1-ε)-approximation that works in near-linear time: In O((n/ε4) log3 n log(1/ε)) time we find an axis-parallel rectangle of area at most α that, with high probability, covers at least (1-ε)κ* points, where κ* is the maximum possible number of points that could be covered.

Original languageEnglish
Pages (from-to)207-222
Number of pages16
JournalJournal of Computational Geometry
Issue number1
Publication statusPublished - 2019


Dive into the research topics of 'Covering many points with a small-area box'. Together they form a unique fingerprint.

Cite this