2026-07-23T05:17:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7860 2024-03-06T10:41:21Z ddc:004 open_access

Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points Kaplan, Haim Roy, Sasanka Sharir, Micha Computational geometry geometric optimization rectangles perimeter area 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haim Kaplan and Sasanka Roy and Micha Sharir 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.52 urn:nbn:de:0030-drops-78608 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.52 eng https://creativecommons.org/licenses/by/3.0/legalcode