Akademik Veri Yönetim Sistemi
19th Annual European Symposium on Algorithms (ESA), Saarbrücken, Almanya, 5 - 09 Eylül 2011, cilt.6942, ss.591-602
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.