Computing Klee's Measure of Grounded Boxes

Creative Commons License

Yildiz H., Suri S.

ALGORITHMICA, vol.71, no.2, pp.307-329, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 71 Issue: 2
  • Publication Date: 2015
  • Doi Number: 10.1007/s00453-013-9797-9
  • Journal Name: ALGORITHMICA
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.307-329
  • Keywords: Grounded boxes, Hypervolume indicator, Klee's measure, Sum of ordered products, Weighted volume, OPTIMA
  • Middle East Technical University Affiliated: No

Abstract

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.