The union volume estimation problem asks to (1±ε) -approximate the volume of the union of n given objects X₁, …, Xₙ ⊂ ℝᵈ. 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ᵢ can be accessed via three types of queries: obtain the volume of Xᵢ, sample a random point from Xᵢ, and test whether Xᵢ 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.
Bhore et al. (Thu,) studied this question.