Covering many points with a small-area box

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 206
  • Download : 0
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. © 2019, Macodrum library, Carleton University. All rights reserved.
Publisher
MacOdrum Library, Carleton University
Issue Date
2019-01
Language
English
Article Type
Article
Citation

Journal of computational geometry, v.10, no.1, pp.207 - 222

ISSN
1920-180X
DOI
10.20382/jocg.v10i1a8
URI
http://hdl.handle.net/10203/271978
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0