TY - JOUR

T1 - Time and space efficient collinearity indexing

AU - Aronov, Boris

AU - Ezra, Esther

AU - Sharir, Micha

AU - Zigdon, Guy

N1 - Funding Information:
Work by Boris Aronov was partially supported by NSF grants CCF-15-40656 and CCF-20-08551 and by grant 2014/170 from the U.S.-Israel Binational Science Foundation . Work by Esther Ezra was partially supported by NSF CAREER under grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation . Work by Micha Sharir was partially supported by Grant 260/18 from the Israel Science Foundation .
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2023/3

Y1 - 2023/3

N2 - 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∈R2, 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].

AB - 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∈R2, 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].

KW - 3SUM-indexing

KW - Collinearity testing

KW - Computational geometry

KW - Function inversion

UR - http://www.scopus.com/inward/record.url?scp=85142149735&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85142149735&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2022.101963

DO - 10.1016/j.comgeo.2022.101963

M3 - Article

AN - SCOPUS:85142149735

VL - 110

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

M1 - 101963

ER -