On Klee's measure problem for grounded boxes

Download

index.pdf

Date

2012-07-23

Author

Yıldız, Hakan

Metadata

Show full item record

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

Item Usage Stats

39
views

32
downloads

A well-known problem in computational geometry is Klee's measure problem, which asks for the volume of a union of axis-aligned boxes in d-space. In this paper, we consider Klee's measure problem for the special case where a 2-dimensional orthogonal projection of all the boxes has a common corner. We call such a set of boxes 2-grounded and, more generally, a set of boxes is k-grounded if in a k-dimensional orthogonal projection they share a common corner. Our main result is an O(n (d-1)/2 log 2 n) time algorithm for computing Klee's measure for a set of n 2-grounded boxes. This is an improvement of roughly O(√n) compared to the fastest solution of the general problem. The algorithm works for k-grounded boxes, for any k > 2, and in the special case of k = d, also called the hypervolume indicator problem, the time bound can be improved further by a logn factor. The key idea of our technique is to reduce the d-dimensional problem to a semi-dynamic weighted volume problem in dimension d - 2. The weighted volume problem requires solving a combinatorial problem of maintaining the sum of ordered products, which may be of independent interest. Copyright © 2012 ACM.

URI

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

DOI

https://doi.org/10.1145/2261250.2261267

Conference Name

28th Annual Symposuim on Computational Geometry, SCG 2012

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Computing Klee's Measure of Grounded Boxes Yıldız, Hakan (2015-02-01) A well-known problem in computational geometry is Klee's measure problem, which asks for the volume of a union of axis-aligned boxes in d-space. In this paper, we consider Klee's measure problem for the special case where a 2-dimensional orthogonal projection of all the boxes has a common corner. We call such a set of boxes 2-grounded and, more generally, a set of boxes is k-grounded if in a k-dimensional orthogonal projection they share a common corner.
Quantum Hall effect on odd spheres Coskun, U. H.; Kürkcüoğlu, Seçkin; Toga, G. C. (2017-03-22) We solve the Landau problem for charged particles on odd dimensional spheres S2k-1 in the background of constant SO(2k - 1) gauge fields carrying the irreducible representation (I/2,I/2, . . . , I/2). We determine the spectrum of the Hamiltonian, the degeneracy of the Landau levels and give the eigenstates in terms of the Wigner D-functions, and for odd values of I, the explicit local form of the wave functions in the lowest Landau level (LLL). The spectrum of the Dirac operator on S2k-1 in the same gauge f...
On the Poisson sum formula for analysis of EM radiation/scattering from large finite arrays Aydın Çivi, Hatice Özlem; Chou, HT (1998-01-01) A useful procedure, that has been described previously in the literature, employs the Poisson sum formula to represent the solution to the fields of a three-dimensional (3D) large periodically spaced finite planar array problem configuration as a convolution of the infinite planar periodic array solution and the Fourier transform of the equivalent aperture distribution over the finite array. It is shown here that the Poisson sum formula utilized by Felsen and Carin (see J. Opt. Soc. Am. A, vol.11, no.4, p.1...
IMPROVING ITERATIVE SOLUTIONS OF THE ELECTRIC-FIELD INTEGRAL EQUATION VIA TRANSFORMATIONS INTO NORMAL EQUATIONS Ergül, Özgür Salih (Informa UK Limited, 2010-01-01) We consider the solution of electromagnetics problems involving perfectly conducting objects formulated with the electric-field integral equation (EFIE). Dense matrix equations obtained from the discretization of EFIE are solved iteratively by the generalized minimal residual (GMRES) algorithm accelerated with a parallel multilevel fast multipole algorithm. We show that the number of iterations is halved by transforming the original matrix equations into normal equations. This way, memory required for the G...
On a problem of Osserman in Lorentzian geometry GarciaRio, E; Kupeli, DN; VazquezAbal, ME (Elsevier BV, 1997-03-01) A problem of Osserman on the constancy of the eigenvalues of the Jacobi operator is studied in Lorentzian geometry. Attention is paid to the different cases of timelike, spacelike and null Osserman condition. One also shows a relation between the null Osserman condition and a previous one on infinitesimal null isotropy.

Citation Formats

H. Yıldız, “On Klee’s measure problem for grounded boxes,” presented at the 28th Annual Symposuim on Computational Geometry, SCG 2012, Chapel Hill, NC, Amerika Birleşik Devletleri, 2012, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93565.