A (slightly) faster algorithm for klee's measure problem
A (slightly) faster algorithm for klee's measure problem
复制标题
克利测量问题的（稍微）更快的算法
DOI：
10.1145/1377676.1377693
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan
中科院分区：
文献类型：
--
作者：
Timothy M. Chan
给定<i>n</i>个平行于轴的盒子，在一个固定的维度<i>d</i>≥ 3，我们能多有效地计算并集的体积？这个标准的问题在计算几何，通常被称为<i>克利的措施问题</i>，可以解决时间<i>O</i>（<i>n<sup>d/2</sup></i>log<i>n</i>）的算法奥维马斯和雅普（FOCS 1988）。我们给出了第一个（虽然很小）的改进：我们的新算法运行时间<i>为n<sup>d/2</sup></i>2<sup><i>O</i></sup>（log<sup>*</sup><i>n</i>），其中log<sup>*</sup>表示迭代对数。
对于计算<i>n</i>个盒子排列中的<i>深度</i>的相关问题，我们进一步改进了时间约束，使其接近<i>O</i>（<i>n<sup>d/2</sup></i>log<i><sup>d/2-1</sup></i><i>n</i>），忽略log\log<i>n</i>因子。其他应用和下限的可能性进行了讨论。改进算法背后的想法很简单。
Given <i>n</i> axis-parallel boxes in a fixed dimension <i>d</i> ≥ 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as <i>Klee's measure problem</i>, can be solved in time <i>O</i>(<i>n<sup>d/2</sup></i> log <i>n</i>) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time <i>n<sup>d/2</sup></i>2<sup><i>O</i></sup>(log<sup>*</sup><i>n</i>), where log<sup>*</sup> denotes the iterated logarithm.
For the related problem of computing the <i>depth</i> in an arrangement of <i>n</i> boxes, we further improve the time bound to near <i>O</i>(<i>n<sup>d/2</sup></i> log<i><sup>d/2-1</sup></i> <i>n</i>), ignoring log\log <i>n</i> factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.