Name
Title | ||
|---|---|---|
Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points |
Abstract | ||
|---|---|---|
Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O(n5/2logn) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O(nk3/2logk) time, and (ii) an approximation algorithm that finds, in O(n+nkε5log5/2nklog(1εlognk)) time, a rectangle of the given perimeter that contains at least (1−ε)k points of P, where k is the optimum value. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.comgeo.2019.01.007 | Computational Geometry |
Keywords | Field | DocType |
Axis-parallel rectangle,Perimeter,Diagonal,Area,Enclose points | Discrete mathematics,Combinatorics,Computer science,Perimeter | Conference |
Volume | ISSN | Citations |
81 | 0925-7721 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haim Kaplan | 1 | 3581 | 263.96 |
| Sasanka Roy | 2 | 31 | 13.37 |
| Micha Sharir | 3 | 8405 | 1183.84 |