TY - JOUR

T1 - Covering many points with a small-area box

AU - de Berg, Mark T.

AU - Cabello, Sergio

AU - Cheong, Otfried

AU - Eppstein, David

AU - Knauer, Christian

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85073297435&partnerID=8YFLogxK

U2 - 10.20382/jocg.v10i1a8

DO - 10.20382/jocg.v10i1a8

M3 - Article

AN - SCOPUS:85073297435

VL - 10

SP - 207

EP - 222

JO - Journal of Computational Geometry

JF - Journal of Computational Geometry

SN - 1920-180X

IS - 1

ER -