Geometric Pattern Matching Reduces to k-SUM.

DOI10.4230/lipics.isaac.2020.32OpenAlexW3117057551MaRDI QIDQ6065434

Jean Cardinal, Boris Aronov

Publication date: 14 November 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.32

zbMATH Keywords

geometric pattern matchinglinear decision trees\(k\)-SUM problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the number of similar instances of a pattern in a finite set
• Improved subquadratic 3SUM
• Geometric pattern matching under Euclidean motion
• Geometric pattern matching for point sets in the plane under similarity transformations
• Combinatorial geometry problems in pattern recognition
• The number of congruent simplices in a point set
• Combinatorial and experimental methods for approximate point pattern matching
• On the maximum number of equilateral triangles. I
• Subquadratic algorithms for algebraic 3SUM
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Structural results for planar sets with many similar subsets
• Threesomes, Degenerates, and Love Triangles
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Solving k-SUM using few linear queries
• Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Near-optimal Linear Decision Trees for k-SUM and Related Problems
• Lower bounds for linear degeneracy testing
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.

This page was built for publication: Geometric Pattern Matching Reduces to k-SUM.