Geometric pattern matching reduces to \(k\)-SUM
From MaRDI portal
Publication:2172655
DOI10.1007/s00454-021-00324-1OpenAlexW3203304100MaRDI QIDQ2172655
Publication date: 16 September 2022
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.11890
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (1)
Cites Work
- 3SUM, 3XOR, triangles
- 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
- All non-trivial variants of 3-LDT are equivalent
- 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.
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Geometric pattern matching reduces to \(k\)-SUM
