Smallest k-enclosing rectangle revisited

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(n5/2)-time algorithm by Kaplan et al. [23]. 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(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.

Original languageEnglish (US)
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771047
DOIs
StatePublished - Jun 1 2019
Event35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States
Duration: Jun 18 2019Jun 21 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume129
ISSN (Print)1868-8969

Conference

Conference35th International Symposium on Computational Geometry, SoCG 2019
CountryUnited States
CityPortland
Period6/18/196/21/19

Fingerprint

Approximation algorithms
Convolution

Keywords

  • Approximation algorithms
  • Conditional lower bounds
  • Geometric optimization
  • Outliers

ASJC Scopus subject areas

  • Software

Cite this

Chan, T. M-Y., & Har-Peled, S. (2019). Smallest k-enclosing rectangle revisited. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [23] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 129). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2019.23

Smallest k-enclosing rectangle revisited. / Chan, Timothy Moon-Yew; Har-Peled, Sariel.

35th International Symposium on Computational Geometry, SoCG 2019. ed. / Gill Barequet; Yusu Wang. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 23 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 129).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chan, TM-Y & Har-Peled, S 2019, Smallest k-enclosing rectangle revisited. in G Barequet & Y Wang (eds), 35th International Symposium on Computational Geometry, SoCG 2019., 23, Leibniz International Proceedings in Informatics, LIPIcs, vol. 129, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 35th International Symposium on Computational Geometry, SoCG 2019, Portland, United States, 6/18/19. https://doi.org/10.4230/LIPIcs.SoCG.2019.23
Chan TM-Y, Har-Peled S. Smallest k-enclosing rectangle revisited. In Barequet G, Wang Y, editors, 35th International Symposium on Computational Geometry, SoCG 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 23. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.SoCG.2019.23
Chan, Timothy Moon-Yew ; Har-Peled, Sariel. / Smallest k-enclosing rectangle revisited. 35th International Symposium on Computational Geometry, SoCG 2019. editor / Gill Barequet ; Yusu Wang. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs).
@inproceedings{6abdfc449d9b440894d9e22262020adf,
title = "Smallest k-enclosing rectangle revisited",
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(n5/2)-time algorithm by Kaplan et al. [23]. 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(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 = "Approximation algorithms, Conditional lower bounds, Geometric optimization, Outliers",
author = "Chan, {Timothy Moon-Yew} and Sariel Har-Peled",
year = "2019",
month = "6",
day = "1",
doi = "10.4230/LIPIcs.SoCG.2019.23",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Gill Barequet and Yusu Wang",
booktitle = "35th International Symposium on Computational Geometry, SoCG 2019",

}

TY - GEN

T1 - Smallest k-enclosing rectangle revisited

AU - Chan, Timothy Moon-Yew

AU - Har-Peled, Sariel

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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(n5/2)-time algorithm by Kaplan et al. [23]. 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(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.

AB - 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(n5/2)-time algorithm by Kaplan et al. [23]. 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(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.

KW - Approximation algorithms

KW - Conditional lower bounds

KW - Geometric optimization

KW - Outliers

UR - http://www.scopus.com/inward/record.url?scp=85068066014&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068066014&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2019.23

DO - 10.4230/LIPIcs.SoCG.2019.23

M3 - Conference contribution

AN - SCOPUS:85068066014

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Computational Geometry, SoCG 2019

A2 - Barequet, Gill

A2 - Wang, Yusu

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -