The Union of Probabilistic Boxes: Maintaining the Volume

Creative Commons License

Yildiz H., Foschini L., Hershberger J., Suri S.

19th Annual European Symposium on Algorithms (ESA), Saarbrücken, Germany, 5 - 09 September 2011, vol.6942, pp.591-602 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 6942
  • Doi Number: 10.1007/978-3-642-23719-5_50
  • City: Saarbrücken
  • Country: Germany
  • Page Numbers: pp.591-602
  • Middle East Technical University Affiliated: No


Suppose we have a set of n axis-aligned rectangular boxes in d-space, {B-1, B-2,..., B-n}, where each box B-i is active (or present) with an independent probability pi. 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) log n) 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.