License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.26
URN: urn:nbn:de:0030-drops-155373
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15537/
Go to the corresponding LIPIcs Volume Portal

Klimenko, Georgiy ; Raichel, Benjamin

Fast and Exact Convex Hull Simplification

pdf-format:
LIPIcs-FSTTCS-2021-26.pdf (0.7 MB)

Abstract

Given a point set P in the plane, we seek a subset Q ⊆ P, whose convex hull gives a smaller and thus simpler representation of the convex hull of P. Specifically, let cost(Q,P) denote the Hausdorff distance between the convex hulls CH(Q) and CH(P). Then given a value ε > 0 we seek the smallest subset Q ⊆ P such that cost(Q,P) ≤ ε. We also consider the dual version, where given an integer k, we seek the subset Q ⊆ P which minimizes cost(Q,P), such that |Q| ≤ k. For these problems, when P is in convex position, we respectively give an O(n log²n) time algorithm and an O(n log³n) time algorithm, where the latter running time holds with high probability. When there is no restriction on P, we show the problem can be reduced to APSP in an unweighted directed graph, yielding an O(n^2.5302) time algorithm when minimizing k and an O(min{n^2.5302, kn^2.376}) time algorithm when minimizing ε, using prior results for APSP. Finally, we show our near linear algorithms for convex position give 2-approximations for the general case.

BibTeX - Entry

@InProceedings{klimenko_et_al:LIPIcs.FSTTCS.2021.26,
  author =	{Klimenko, Georgiy and Raichel, Benjamin},
  title =	{{Fast and Exact Convex Hull Simplification}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15537},
  URN =		{urn:nbn:de:0030-drops-155373},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.26},
  annote =	{Keywords: Convex hull, coreset, exact algorithm}
}

Keywords: Convex hull, coreset, exact algorithm
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021

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