Covering many points with a small-area box

DOI10.20382/JOCG.V10I1A8MaRDI QIDQ5233323zbMATH OpenOpenAlexFDO

Authors S. Cabello, David Eppstein, Christian Knauer, Mark de Berg, Otfried Cheong

Publication date 10 September 2019

Full work available at URL https://arxiv.org/abs/1612.02149

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: 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(n{k}^{2}logn+nlo{g}^{2}n)$ time. We also consider the problem of, given a value $alpha>0$, covering as many points of $P$ as possible with an axis-parallel rectangle of area at most $alpha$. For this problem we give a probabilistic $(1-varepsilon)$-approximation that works in near-linear time: In $O((n/varepsilo{n}^4)lo{g}^{3}nlog(1/varepsilon))$ time we find an axis-parallel rectangle of area at most $alpha$ that, with high probability, covers at least $(1-varepsilon)mathrmkapp{a}^{\ast }$ points, where $mathrmkapp{a}^{\ast }$ is the maximum possible number of points that could be covered.

Recommendations

• Enclosing k points in the smallest axis parallel rectangle
• Square and Rectangle Covering with Outliers
• Covering points by disjoint boxes with outliers
• scientific article; zbMATH DE number 7205030
• Covering a set of points by two axis-parallel boxes

Cited in

(15)

• Covering a set of points in multidimensional space
• Covering points with convex sets of minimum size
• Smallest \(k\)-enclosing rectangle revisited
• The maximum exposure problem
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• A good sampling method for guessing rectangles in \([0,1]^2\)
• Enclosing k points in the smallest axis parallel rectangle
• Covering a set of points by two axis-parallel boxes
• Covering a Set of Points with a Minimum Number of Lines
• Selecting Heavily Covered Points
• On finding the maximum and minimum density axes-parallel regions in R^d
• Smallest k-enclosing rectangle revisited
• scientific article; zbMATH DE number 7205030 (Why is no real title available?)
• Square and Rectangle Covering with Outliers
• Covering points by disjoint boxes with outliers

This page was built for publication: Covering many points with a small-area box

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233323)