A discrete and dynamic version of klee's measure problem

Date

2011-12-01

Author

Yıldız, Hakan
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

21
views

0
downloads

Given a set of axis-aligned boxes B = {B1,B2, . . . ,Bn} and a set of points P = {p1, p2, . . ., pm} in d-space, let the discrete measure of B with respect to P be defined as meas(B,P) = P ∩ { ∪n i=1 Bi}, namely, the number of points of P contained in the union of boxes of B. This is a discrete and dynamic version of Klee's measure problem, which asks for the Euclidean volume of a union of boxes. Our result is a data structure for maintaining meas(B,P) under dynamic updates to both P and B, with O(log d n + m1-1/d ) time for each insert or delete operation in B, O(logd n + logm) time for each insert and O(logm) time for each delete operation in P, and O(1) time for the measure query. Our bound is slightly better than what can be achieved by applying a more general technique of Chan [3], but the primary appeal is that the method is simpler and more direct.

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84882971595&origin=inward
https://hdl.handle.net/11511/94103

Conference Name

23rd Annual Canadian Conference on Computational Geometry, CCCG 2011

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

A New Combinatorial Identity for Catalan Numbers Aker, Kursat; Gursoy, Aysin Erkan (2017-10-01) In this article, we prove a conjecture about the equality of two generating functions described in "From Parking Functions to Gelfand Pairs (Aker, Can 2012)" attached to two sets whose cardinalities are given by Catalan numbers: We establish a combinatorial bijection between the two sets on which the two generating functions were based on.
On Verification of Restricted Extended Affine Equivalence of Vectorial Boolean Functions Özbudak, Ferruh; Yayla, Oğuz (2015-02-01) Vectorial Boolean functions are used as substitution boxes in cryptosystems. Designing inequivalent functions resistant to known attacks is one of the challenges in cryptography. In doing this, finding a fast technique for determining whether two given functions are equivalent is a significant problem. A special class of the equivalence called restricted extended affine (REA) equivalence is studied in this paper. We update the verification procedures of the REA-equivalence types given in the recent work of ...
On the number of topologies on a finite set Kızmaz, Muhammet Yasir (2019-01-01) We denote the number of distinct topologies which can be defined on a set X with n elements by T(n). Similarly, T-0(n) denotes the number of distinct T-0 topologies on the set X. In the present paper, we prove that for any prime p, T(p(k)) k+ 1 (mod p), and that for each natural number n there exists a unique k such that T(p + n) k (mod p). We calculate k for n = 0, 1, 2, 3, 4. We give an alternative proof for a result of Z. I. Borevich to the effect that T-0(p + n) T-0(n + 1) (mod p).
A note on the transfinite diameter of Bernstein sets Yazıcı, Özcan (2022-01-01) A compact set K subset of C-n is called Bernstein set if, for some constant M > 0, the following inequality
On the special values of monic polynomials of hypergeometric type Taşeli, Hasan (Springer Science and Business Media LLC, 2008-01-01) Special values of monic polynomials y(n)(s), with leading coefficients of unity, satisfying the equation of hypergeometric type

Citation Formats

H. Yıldız and S. Suri, “A discrete and dynamic version of klee’s measure problem,” presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, Kanada, 2011, Accessed: 00, 2021. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84882971595&origin=inward.