Computing Klee's Measure of Grounded Boxes
ALGORITHMICA, vol.71, no.2, pp.307-329, 2015 (SCI-Expanded, Scopus)
- 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
- Open Archive Collection: AVESIS Open Access Collection
- 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.