Time and space efficient collinearity indexing

DOI10.1016/J.COMGEO.2022.101963MaRDI QIDQ2678263zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Esther Ezra, Guy Zigdon, Micha Sharir

Publication date 9 January 2023

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2022.101963

zbMATH Keywords

3\textsc{sum}-indexingcollinearity testingcomputational geometryfunction inversion

Mathematics Subject Classification ID

Theory of computing (68Qxx) Computing methodologies and applications (68Uxx) Algorithms in computer science (68Wxx)

Recommendations

• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Enumerating Collinear Points in Higher Dimensions
• On 3SUM-hard problems in the decision tree model
• Lines in space: Combinatorics and algorithms

Cites work

• Algorithms in real algebraic geometry
• Computational geometry. Algorithms and applications.
• Data structures meet cryptography: 3SUM with preprocessing
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Improved subquadratic 3SUM
• Introduction to algorithms.
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Near-optimal linear decision trees for \(k\)-SUM and related problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• Rigorous Time/Space Trade-offs for Inverting Functions
• Simplex Range Searching and Its Variants: A Review
• Space-time trade-offs for some ranking and searching queries
• Subquadratic algorithms for algebraic 3SUM
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Threesomes, degenerates, and love triangles

Cited in

(2)

• A general technique for searching in implicit sets via function inversion
• Improved space-efficient approximate nearest neighbor search using function inversion

This page was built for publication: Time and space efficient collinearity indexing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2678263)