2026-07-23T06:18:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5919 2024-03-06T10:37:17Z ddc:004 open_access

Dynamic Streaming Algorithms for Epsilon-Kernels Chan, Timothy M. coresets streaming algorithms dynamic algorithms polynomial method randomization outliers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.27 urn:nbn:de:0030-drops-59198 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.27 eng https://creativecommons.org/licenses/by/3.0/legalcode