Time and space efficient collinearity indexing
Time and space efficient collinearity indexing
复制标题
DOI：
10.1016/j.comgeo.2022.101963
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
B. Aronov;Esther Ezra;M. Sharir;Guy Zigdon
中科院分区：
文献类型：
--
作者：
B. Aronov;Esther Ezra;M. Sharir;Guy Zigdon
共线检验问题是计算几何中的一个基本问题，给定平面上的三个集合A，B，C，每个集合n个点，其任务是在A× B× C中检测出一个共线的点三元组或报告不存在这样的三元组。在本文中，我们考虑这个问题的一个预处理变体，即共线索引问题，在这个问题中，我们给定两个集合A和B，每个集合在平面上有n个点，我们的目标是将A和B预处理成一个数据结构，这样，对于任意查询点q∈ R2，我们可以确定q是否与一对点（a，B）∈ A× B共线.针对A、B的点位于整数网格上，而查询点位于垂直线上的情况，提出了一种次二次存储和次线性查询时间的数据结构。然后，我们将结果扩展到查询点位于常次数多项式图上的情况。我们的解决方案基于Fiat和Naor的函数反演技术[11]。
The collinearity testing problem is a basic problem in computational geometry, in which, given three sets A, B, C in the plane, of n points each, the task is to detect a collinear triple of points in A× B× C or report there is no such triple. In this paper we consider a preprocessing variant of this question, namely, the collinearity indexing problem, in which we are given two sets A and B, each of n points in the plane, and our goal is to preprocess A and B into a data structure, so that, for any query point q∈ R 2, we can determine whether q is collinear with a pair of points (a, b)∈ A× B. We provide a solution to the problem for the case where the points of A, B lie on an integer grid, and the query points lie on a vertical line, with a data structure of subquadratic storage and sublinear query time. We then extend our result to the case where the query points lie on the graph of a polynomial of constant degree. Our solution is based on the function-inversion technique of Fiat and Naor [11].