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.2016.27
URN: urn:nbn:de:0030-drops-59198
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5919/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M.

Dynamic Streaming Algorithms for Epsilon-Kernels

pdf-format:
LIPIcs-SoCG-2016-27.pdf (0.5 MB)

Abstract

Introduced by Agarwal, Har-Peled, and Varadarajan [J. ACM, 2004], an epsilon-kernel of a point set is a coreset that can be used to approximate the width, minimum enclosing cylinder, minimum bounding box, and solve various related geometric optimization problems. Such coresets form one of the most important tools in the design of linear-time approximation algorithms in computational geometry, as well as efficient insertion-only streaming algorithms and dynamic (non-streaming) data structures. In this paper, we continue the theme and explore dynamic streaming algorithms (in the so-called turnstile model).

Andoni and Nguyen [SODA 2012] described a dynamic streaming algorithm for maintaining a (1+epsilon)-approximation of the width using O(polylog U) space and update time for a point set in [U]^d for any constant dimension d and any constant epsilon>0. Their sketch, based on a "polynomial method", does not explicitly maintain an epsilon-kernel. We extend their method to maintain an epsilon-kernel, and at the same time reduce some of logarithmic factors. As an application, we obtain the first randomized dynamic streaming algorithm for the width problem (and related geometric optimization problems) that supports k outliers, using poly(k, log U) space and time.

BibTeX - Entry

@InProceedings{chan:LIPIcs:2016:5919,
  author =	{Timothy M. Chan},
  title =	{{Dynamic Streaming Algorithms for Epsilon-Kernels}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{27:1--27:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5919},
  URN =		{urn:nbn:de:0030-drops-59198},
  doi =		{10.4230/LIPIcs.SoCG.2016.27},
  annote =	{Keywords: coresets, streaming algorithms, dynamic algorithms, polynomial method, randomization, outliers}
}

Keywords: coresets, streaming algorithms, dynamic algorithms, polynomial method, randomization, outliers
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

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