The Union of Probabilistic Boxes: Maintaining the Volume

Abstract

Suppose we have a set of n axis-aligned rectangular boxes in d-space, {B ₁, B ₂, …, B _n }, where each box B _i is active (or present) with an independent probability p _i . We wish to compute the expected volume occupied by the union of all the active boxes. Our main result is a data structure for maintaining the expected volume over a dynamic family of such probabilistic boxes at an amortized cost of O(n ^{(d − 1)/2}logn) time per insert or delete. The core problem turns out to be one-dimensional: we present a new data structure called an anonymous segment tree, which allows us to compute the expected length covered by a set of probabilistic segments in logarithmic time per update. Building on this foundation, we then generalize the problem to d dimensions by combining it with the ideas of Overmars and Yap [13]. Surprisingly, while the expected value of the volume can be efficiently maintained, we show that the tail bounds, or the probability distribution, of the volume are intractable—specifically, it is NP-hard to compute the probability that the volume of the union exceeds a given value V even when the dimension is d = 1.