2026-07-24T01:58:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24248 2025-11-12T13:39:24Z ddc:004 open_access

Dynamic Streaming Algorithms for Geometric Independent Set Chan, Timothy M. Yu, Yuancheng Geometric Independent Set Dynamic Streaming Algorithms We present the first space-efficient, fully dynamic streaming algorithm for computing a constant-factor approximation of the maximum independent set size of n axis-aligned rectangles in two dimensions. For an arbitrarily small constant δ > 0, our algorithm obtains an O((1/δ)²) approximation and requires O(U^δ polylog n) space and update time with high probability, assuming that coordinates are integers bounded by U. We also obtain a similar result for fat objects in any constant dimension. This extends recent non-streaming algorithms by Bhore and Chan from SODA'25, and also greatly extends previous streaming results, which were limited to special types of geometric objects such as one-dimensional intervals and unit disks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Yuancheng Yu 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.17 urn:nbn:de:0030-drops-242481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.17 eng https://creativecommons.org/licenses/by/4.0/legalcode