Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
20
views
15
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.