We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space.
展开▼
机译:我们为计算几何中的标准问题提供了第一个最佳解决方案:三维半空间范围报告。我们证明了3-d中的n个点可以存储在线性空间数据结构中,这样查询半空间内的所有k个点都可以在O(log n + k)的时间内报告。可以在O(n log n)的预期时间内构建数据结构。具有最佳查询时间的先前方法需要超线性(O(n log log n))空间。
展开▼