Smallest k -Enclosing Rectangle Revisited
- PDF / 675,077 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 215 Views
Smallest k-Enclosing Rectangle Revisited Timothy M. Chan1
· Sariel Har-Peled1
Received: 16 July 2019 / Revised: 18 June 2020 / Accepted: 25 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given a set of n points in the plane, and a parameter k, we consider the problem of computing the minimum (perimeter or area) axis-aligned rectangle enclosing k points. We present the first near quadratic time algorithm for this problem, improving over the previous near-O(n 5/2 )-time algorithm by Kaplan et al. (25th European Symposium on Algorithms. Leibniz Int Proc Inform, vol. 87, # 52. Leibniz-Zent Inform, Wadern, 2017). We provide an almost matching conditional lower bound, under the assumption that (min, +)-convolution cannot be solved in truly subquadratic time. Furthermore, we present a new reduction (for both perimeter and area) that can make the time bound sensitive to k, giving near O(nk) time. We also present a near linear time (1 + ε)approximation algorithm to the minimum area of the optimal rectangle containing k points. In addition, we study related problems including the 3-sided, arbitrarily oriented, weighted, and subset sum versions of the problem. Keywords Geometric optimization · Outliers · Approximation algorithms · Conditional lower bounds Mathematics Subject Classification 68Q25 · 68U05
Editor in Charge: Kenneth Clarkson A preliminary version of this paper appeared in SoCG 2019 [12]. Timothy M. Chan [email protected] Sariel Har-Peled [email protected] 1
Department of Computer Science, University of Illinois, 201 N. Goodwin Avenue, Urbana, IL 61801, USA
123
Discrete & Computational Geometry
1 Introduction Given a set P of n points in the plane, and a parameter k, consider the problem of computing the smallest area/perimeter axis-aligned rectangle that contains k points of P. (Unless stated otherwise, rectangles are axis-aligned by default.) This problem and its variants have a long history. Eppstein and Erickson [19] studied an exhaustive number of variants of this problem for various shapes. For the minimum perimeter variant, the first work on this problem seems to be Aggarwal et al. [1], who showed a brute force algorithm with running time O(n 3 ). Recently, Kaplan et al. [24] gave an algorithm with running time O(n 5/2 log2 n) that works for both minimum perimeter and area. Several works derived algorithms with running time sensitive to k, the number of points in the shape. Aggarwal et al. [1] showed an algorithm for the minimum perimeter with running time O(k 2 n log n). This was improved to O(n log n + k 2 n) by Eppstein and Erickson [19] or alternatively by Datta et al. [18]. Kaplan et al.’s algorithm [24] for the k-insensitive case, coupled with these previous techniques [18,19], results in an O(n log n + nk 3/2 log2 k) running time, which is currently the state of the art. Known techniques [18,19] reduce the problem to solving O(n/k) instances of size O(k). These reductions work only for the perimeter case, not the area case—in particular, there are in
Data Loading...
