The Union of Probabilistic Boxes: Maintaining the Volume

Download

index.pdf

Date

2011-01-01

Author

Yıldız, Hakan
Hershberger, John
Suri, Subhash

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

59
views

68
downloads

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.

URI

https://hdl.handle.net/11511/93998

DOI

https://doi.org/10.1007/978-3-642-23719-5_50

Conference Name

19th Annual European Symposium on Algorithms (ESA)

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Improved Polynomial Multiplication Formulas over F-2 Using Chinese Remainder Theorem Cenk, Murat; Özbudak, Ferruh (2009-04-01) Let n and l be positive integers and f(x) be an irreducible polynomial over F-2 such that ldeg(f(x)) < 2n - 1. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f(x)(l). This upper bound allows a better selection of the moduli when the Chinese Remainder Theorem is used for polynomial multiplication over F-2. We give improved formulas to multiply polynomials of small degree over F-2. In particular, we improve the best known multiplication complexities over F-2 ...
Results on complexity of multiplication over finite fields Cenk, Murat; Özbudak, Ferruh; Department of Cryptography (2009) Let n and l be positive integers and f (x) be an irreducible polynomial over Fq such that ldeg( f (x)) < 2n - 1, where q is 2 or 3. We obtain an effective upper bound for the multiplication complexity of n-term polynomials modulo f (x)^l. This upper bound allows a better selection of the moduli when Chinese Remainder Theorem is used for polynomial multiplication over Fq. We give improved formulae to multiply polynomials of small degree over Fq. In particular we improve the best known multiplication complexi...
Memorandum on multiplicative bijections and order Cabello Sanchez, Felix; Cabello Sanchez, Javier; ERCAN, ZAFER; Önal, Süleyman (Springer Science and Business Media LLC, 2009-08-01) Let C(X, I) denote the semigroup of continuous functions from the topological space X to I = [0, 1], equipped with the pointwise multiplication. The paper studies semigroup homomorphisms C(Y, I) -> C(X, I), with emphasis on isomorphisms. The crucial observation is that, in this setting, homomorphisms preserve order, so isomorphisms preserve order in both directions and they are automatically lattice isomorphisms. Applications to uniformly continuous and Lipschitz functions on metric spaces are given. Sample...
An obstruction to finding algebraic models for smooth manifolds with prescribed algebraic submanifolds CELIKTEN, A; Ozan, Yıldıray (2001-03-01) Let N ⊆ M be a pair of closed smooth manifolds and L an algebraic model for the submanifold N. In this paper, we will give an obstruction to finding an algebraic model X of M so that the submanifold N corresponds in X to an algebraic subvariety isomorphic to L.
On the arithmetic complexity of Strassen-like matrix multiplications Cenk, Murat (2017-05-01) The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Stras...

Citation Formats

H. Yıldız, J. Hershberger, and S. Suri, “The Union of Probabilistic Boxes: Maintaining the Volume,” Saarbrücken, Almanya, 2011, vol. 6942, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93998.