TY - GEN

T1 - A (slightly) faster algorithm for Klee's measure problem

AU - Chan, Timothy M.

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - Given n axis-parallel boxes in a fixed dimension d ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(nd/2 log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n d/22O(log*n), where log* denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n d/2/logd/2-1n), ignoring log log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

AB - Given n axis-parallel boxes in a fixed dimension d ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(nd/2 log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n d/22O(log*n), where log* denotes the iterated logarithm. For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n d/2/logd/2-1n), ignoring log log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.

KW - Boxes

KW - Data structures

KW - Union of geometric objects

UR - http://www.scopus.com/inward/record.url?scp=57349165751&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349165751&partnerID=8YFLogxK

U2 - 10.1145/1377676.1377693

DO - 10.1145/1377676.1377693

M3 - Conference contribution

AN - SCOPUS:57349165751

SN - 9781605580715

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 94

EP - 100

BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08

T2 - 24th Annual Symposium on Computational Geometry, SCG'08

Y2 - 9 June 2008 through 11 June 2008

ER -