DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2021.39

Geometric Cover with Outliers Removal

Authors: Zhengyang Guo and Yi Li

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract

We study the problem of partial geometric cover, which asks to find the minimum number of geometric objects (unit squares and unit disks in this work) that cover at least (n-t) of n given planar points, where 0 ≤ t ≤ n/2. When t = 0, the problem is the classical geometric cover problem, for which many existing works adopt a general framework called the shifting strategy. The shifting strategy is a divide and conquer paradigm which partitions the plane into equal-width strips, applies a local algorithm on each strip and then merges the local solutions with only a small loss on the overall approximation ratio. A challenge to extend the shifting strategy to the case of outliers is to determine the number of outliers in each strip. We develop a shifting strategy incorporating the outlier distribution, which runs in O(tn log n) time. We also develop local algorithms on strips for the outliers case, improving the running time over previous algorithms, and consequently obtain approximation algorithms to the partial geometric cover.

Cite as

Zhengyang Guo and Yi Li. Geometric Cover with Outliers Removal. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.STACS.2021.39,
  author =	{Guo, Zhengyang and Li, Yi},
  title =	{{Geometric Cover with Outliers Removal}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.39},
  URN =		{urn:nbn:de:0030-drops-136849},
  doi =		{10.4230/LIPIcs.STACS.2021.39},
  annote =	{Keywords: Geometric Cover, Unit Square Cover, Unit Disk Cover, Shifting Strategy, Outliers Detection, Computational Geometry}
}

Search Results

Documents authored by Guo, Zhengyang

Geometric Cover with Outliers Removal

Abstract

Cite as

Thanks for your feedback!

Could not send message