2026-07-20T12:08:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25818 2026-06-23T12:58:57Z ddc:004 open_access

Dynamic and Streaming Algorithms for Union Volume Estimation Bhore, Sujoy Bringmann, Karl Chan, Timothy M. Wang, Yanheng union volume estimation dynamic algorithms streaming algorithms The union volume estimation problem asks to (1±ε)-approximate the volume of the union of n given objects X₁,…,X_n ⊂ ℝ^d. In their seminal work in 1989, Karp, Luby, and Madras solved this problem in time O(n/ε²) in an oracle model where each object X_i can be accessed via three types of queries: obtain the volume of X_i, sample a random point from X_i, and test whether X_i contains a given point x. This running time was recently shown to be optimal [Bringmann, Larsen, Nusser, Rotenberg, and Wang, SoCG'25]. In another line of work, Meel, Vinodchandran, and Chakraborty [PODS'21] designed algorithms that read the objects in one pass using polylogarithmic time per object and polylogarithmic space; this can be phrased as a dynamic algorithm supporting insertions of objects for union volume estimation in the oracle model. In this paper, we study algorithms for union volume estimation in the oracle model that support both insertions and deletions of objects. We obtain the following results: 1) an algorithm supporting insertions and deletions in polylogarithmic update and query time and linear space (this is the first such dynamic algorithm, even for 2D triangles); 2) an algorithm supporting insertions and suffix queries (which generalizes the sliding window setting) in polylogarithmic update and query time and space; 3) an algorithm supporting insertions and deletions of convex bodies of constant dimension in polylogarithmic update and query time and space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Karl Bringmann and Timothy M. Chan and Yanheng Wang 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.12 urn:nbn:de:0030-drops-258180 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode