Some techniques for geometric searching with implicit set representations
Some techniques for geometric searching with implicit set representations
复制标题
使用隐式集合表示进行几何搜索的一些技术
作者：
B. Chazelle
总结 当集合的所有元素都可以在内存中表示时，有许多有效的方法来搜索集合。然而，通常搜索范围太大而无法单独存储每个元素，并且必须使用某种隐式表示。在这些条件下是否仍然可以有效地进行搜索是本文的基本主题。我们研究了计算几何中这个问题的多次出现，并提出了各种攻击路线。在此过程中，我们改进了几个具体问题的解决方案；例如，计算顺序统计、执行多边形范围搜索、测试代数谓词等。
SummaryThere are many efficient ways of searching a set when all its elements can be represented in memory. Often, however, the domain of the search is too large to have each element stored separately, and some implicit representation must be used. Whether it is still possible to search efficiently in these conditions is the underlying theme of this paper. We look at several occurrences of this problem in computational geometry and we propose various lines of attack. In the course of doing so, we improve the solutions of several specific problems; for example, computing order statistics, performing polygonal range searching, testing algebraic predicates, etc.