NEW UPPER-BOUNDS IN KLEE MEASURE PROBLEM

被引：93

作者：

OVERMARS, MH ^{[1
]}

YAP, CK ^{[1
]}

机构：

[1] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 06期

关键词：

MEASURE; PARTITION TREES; COMPUTATIONAL GEOMETRY;

D O I：

10.1137/0220065

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

New upper bounds for the measure problem of Klee are given which significantly improve the previous bounds for dimensions greater than two. An O(n(d/2) log n, n) time-space upper bound is obtained and used to compute the measure of a set of n boxes in Euclidean d-space. The solution is based on a new data structure, which is called an orthogonal partition tree. This structure has other applications as well.

引用

页码：1034 / 1045

页数：12