Computing Klee's Measure of Grounded Boxes

Date

2015-02-01

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

46
views

6
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.

URI

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

Journal

ALGORITHMICA

DOI

https://doi.org/10.1007/s00453-013-9797-9

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

On Klee's measure problem for grounded boxes Yıldız, Hakan (2012-07-23) 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 algor...
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...
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...
Obtaining of Time Response from Frequency Response of Fractional Order Systems Avsar, Selman Fatih; HAMAMCI, SERDAR ETHEM (2015-05-19) In this paper, an approximation method for obtaining the unit step response of a fractional order system is presented. The method is based on using piecewise linear equivalence of real frequency response curve of the system. Simulation examples shows that this method gives successful unit step response results for the fractional order systems.
Topology of real cubic fourfolds Finashin, Sergey (2010-01-01) A solution of the problem of topological classification of real cubic fourfolds is given. It is proven that the real locus of a real non-singular cubic fourfold is diffeomorphic either to a connected sum RP(4)#i(S(2) x S(2))# j(S(1) x S(3)) or to a disjoint union RP(4) (sic) S(4).

Citation Formats

H. Yıldız, “Computing Klee’s Measure of Grounded Boxes,” ALGORITHMICA, vol. 71, no. 2, pp. 307–329, 2015, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/93763.