On Klee's measure problem for grounded boxes


Creative Commons License

Yildiz H., Suri S.

28th Annual Symposuim on Computational Geometry, SCG 2012, Chapel Hill, NC, Amerika Birleşik Devletleri, 17 - 20 Haziran 2012, ss.111-120 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1145/2261250.2261267
  • Basıldığı Şehir: Chapel Hill, NC
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.111-120
  • Anahtar Kelimeler: Grounded boxes, Hypervolume indicator, Klee's measure, Sum of ordered products, Weighted volume
  • Orta Doğu Teknik Üniversitesi Adresli: Hayır

Özet

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.