Time and space efficient collinearity indexing

Boris Aronov, Esther Ezra, Micha Sharir, Guy Zigdon

    Research output: Contribution to journalArticlepeer-review


    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].

    Original languageEnglish (US)
    Article number101963
    JournalComputational Geometry: Theory and Applications
    StatePublished - Mar 2023


    • 3SUM-indexing
    • Collinearity testing
    • Computational geometry
    • Function inversion

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'Time and space efficient collinearity indexing'. Together they form a unique fingerprint.

    Cite this