License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.23
URN: urn:nbn:de:0030-drops-104276
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10427/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; Har-Peled, Sariel

Smallest k-Enclosing Rectangle Revisited

pdf-format:
LIPIcs-SoCG-2019-23.pdf (0.7 MB)

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. [Haim Kaplan et al., 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 either perimeter or area) that can make the time bound sensitive to k, giving near O(n k) time. We also present a near linear time (1+epsilon)-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.

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs:2019:10427,
  author =	{Timothy M. Chan and Sariel Har-Peled},
  title =	{{Smallest k-Enclosing Rectangle Revisited}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10427},
  URN =		{urn:nbn:de:0030-drops-104276},
  doi =		{10.4230/LIPIcs.SoCG.2019.23},
  annote =	{Keywords: Geometric optimization, outliers, approximation algorithms, conditional lower bounds}
}

Keywords: Geometric optimization, outliers, approximation algorithms, conditional lower bounds
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI