Computing Klee's Measure of Grounded Boxes

Creative Commons License

Yildiz H., Suri S.

ALGORITHMICA, cilt.71, sa.2, ss.307-329, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 71 Sayı: 2
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1007/s00453-013-9797-9
  • Dergi Adı: ALGORITHMICA
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.307-329
  • Anahtar Kelimeler: Grounded boxes, Hypervolume indicator, Klee's measure, Sum of ordered products, Weighted volume, OPTIMA
  • 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.