Document Open Access Logo

Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points

Authors Haim Kaplan, Sasanka Roy, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.52.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Haim Kaplan
Sasanka Roy
Micha Sharir

Cite As Get BibTex

Haim Kaplan, Sasanka Roy, and Micha Sharir. Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.52

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(n^{5/2} log n) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O(nk^{3/2} log k) time, and (ii) an approximation algorithm that finds, in O(n+(n/(k epsilon^5))*log^{5/2}(n/k)log((1/epsilon) log(n/k))) time, a rectangle of the given perimeter or diagonal that contains at least (1-epsilon)k points of P, where k is the optimum value.

We then show how to turn this algorithm into one that finds, for a given k, an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.

Subject Classification

Keywords
  • Computational geometry
  • geometric optimization
  • rectangles
  • perimeter
  • area

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Aggarwal, H. Imai, N. Katoh, and S. Suri. Finding k points with minimum diameter and related problems. J. Algorithms, 12(1):38-56, 1991. Google Scholar
  2. N. Bansal and S. Garg. Algorithmic discrepancy beyond partial coloring. In Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 914-926, 2017. Google Scholar
  3. Y-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proc. IEEE, 80(9):1412-1434, 1992. Google Scholar
  4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  5. A. Datta, H.P. Lenhof, C. Schwarz, and M. Smid. Static and dynamic algorithms for k-point clustering problems. J. Algorithms, 19(3):474-503, 1995. Google Scholar
  6. M. de Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer. Covering many points with a small-area box. CoRR, abs/1612.02149, 2016. Google Scholar
  7. D. Eppstein and J. Erickson. Iterated nearest neighbors and finding minimal polytopes. Discrete Comput. Geom., 11(3):321-350, 1994. Google Scholar
  8. G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking in X + Y and matrices with sorted columns. J. Comput. Syst. Sci., 24(2):197-208, 1982. Google Scholar
  9. G. N. Frederickson and D. B. Johnson. Finding kth paths and p-centers by generating and searching good data structures. J. Algorithms, 4(1):61-80, 1983. Google Scholar
  10. G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: Sorted matrices. SIAM J. Comput., 13(1):14-30, 1984. Google Scholar
  11. S. Har-peled. Geometric Approximation Algorithms. American Mathematical Society, Boston, MA, USA, 2011. Google Scholar
  12. H. Imai and T. Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms, 4(4):310-323, 1983. Google Scholar
  13. A. Mirzaian and E. Arjomandi. Selection in X + Y and matrices with sorted rows and columns. Information Processing Letters, 20(1):13-17, 1985. Google Scholar
  14. S.C. Nandy and B.B. Bhattacharya. A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids. Computers Math. Applic., 29(8):45-61, 1995. Google Scholar
  15. M. Segal and K. Kedem. Enclosing k points in the smallest axis parallel rectangle. Inform. Process. Letts., 65(2):95-99, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact