【24h】

Approximate Range Searching: The Absolute Model

机译:近似范围搜索:绝对模型

获取原文
获取原文并翻译 | 示例

摘要

Range searching is a well known problem in the area of geometric data structures. We consider this problem in the context of approximation, where an approximation parameter ε > 0 is provided. Most prior work on this problem has focused on the case of relative errors, where each range shape R is bounded, and points within distance ε · diam(R) of the range's boundary may or may not be included. We consider a different approximation model, called the absolute model, in which points within distance ε of the range's boundary may or may not be included, regardless of the diameter of the range. We consider range spaces consisting of halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. We consider a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness. We show how idempotence can be used to improve not only approximate, but also exact halfspace range searching. Our data structures are much simpler than both their exact and relative model counterparts, and so are amenable to efficient implementation.
机译:范围搜索是几何数据结构领域中的一个众所周知的问题。我们在提供近似参数ε> 0的近似情况下考虑这个问题。关于此问题的大多数现有工作都集中在相对误差的情况下,其中每个范围形状R都具有边界,并且可能包含或可能不包含范围边界的距离ε·diam(R)内的点。我们考虑了一个不同的近似模型,称为绝对模型,其中无论范围的直径如何,都可以包括或可以不包括范围边界距离ε内的点。我们考虑范围空间,该范围空间由半空间,欧几里得球,单纯形,与轴对齐的矩形和一般凸体组成。我们考虑各种问题的表述,包括在一般可交换半群,幂等半群,群和空域下的范围搜索。我们展示了如何使用幂等性来改善近似空间以及精确的半空间范围搜索。我们的数据结构比它们的精确模型和相对模型都简单得多,因此可以有效地实现。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号