Geometric Pattern Matching Reduces to k-SUM
Boris Aronov Jean Cardinal
cs.CG cs.DS

Spin textures in chiral magnetic monolayers 
with suppressed nearest-neighbor exchange
    Milorad V. Milošević
    December 30, 2023
======================================================================================




We prove that some exact geometric pattern matching problems reduce in linear time to  when the pattern has a fixed size k. 
This holds in the real RAM model for searching for a similar copy of a set of k≥ 3 points within a set of n points in the plane, and for searching for an affine image of a set of k≥ d+2 points within a set of n points in d-space.


As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.




§ INTRODUCTION


The  problem is a fixed-parameter version of the -complete SUBSET SUM problem.
It consists of deciding, given a set of n numbers, whether any subset of size k sum to zero. The problem for k=3, known as , is now
a well-established bottleneck problem in fine-grained complexity theory (see for instance <cit.> and references therein).
While there are many reductions showing - or -hardness of computational problems in geometry, only few reductions to
 and  are known. We give examples of computational geometry problems that reduce to  or .

Our results are motivated by the nontrivial improved upper bounds on the complexity of  and  proven in the recent years.
While it has long been conjectured that no subquadratic algorithm for  existed, it is now known to be solvable in time O((n^2/log n)(loglog n)^2) in the real RAM model <cit.>. The existence of an O(n^2-δ) algorithm for some δ>0 remains an open problem.
Using folklore meet-in-the-middle algorithms,  can be solved in time O(n^⌈ k/2⌉) if k is odd, and in time O(n^k/2log n) if k is even.
Recently, Kane, Lovett, and Moran <cit.> showed that it can be solved in time O(nlog^2 n) in the linear decision tree model, improving on previous polynomial bounds <cit.>.



  
Geometric pattern matching.

We consider two problems involving searching for a given set P of k points, called the pattern, within a larger set S of points, up to some geometric transformation.
Here we focus on exact algorithms, in which the pattern must match the subset of points exactly.
We consider the following two problems.

[SIMILARITY MATCHING]
  For a fixed integer k≥ 3, given a set P of k points in the plane and a set S of n points in the plane,
  determine whether S contains the image of P under a similarity transformation.


[AFFINE MATCHING]
For fixed integers d≥ 2 and k≥ d+2, given a set P of k points in ℝ^d containing d+1 affinely independent points, and
a set S of n points in ℝ^d, determine whether S contains the image of P under an affine transformation.


A large body of the computational geometry and pattern recognition literature is dedicated to the problems of finding approximate
matches up to some geometric transformation, where the quality of the approximation is typically measured by the Hausdorff distance <cit.>.
For exact pattern matching problems under different families of transformations, known upper bounds on time complexity have been compiled in a survey by Peter Braß <cit.>.
We reproduce them in Table <ref>.



The complexity of these algorithms are directly related to bounds on the maximum number of occurrences of a pattern or a distance in a set of n points.
In fact, such bounds directly yield a lower bound on the computational problem of listing all occurrences of the pattern.
A prototypal example is Erdős' unit distance problem; see Braß and Pach <cit.> for more examples.
It is known, in particular, that there can be Θ(n^2) similar copies of a pattern in an n-point set <cit.>.
Structural results on the extremal point sets are also known <cit.>.
For affine transformations in ℝ^d, there exist pairs P,S such that S contains Θ (n^d+1) copies of P: for instance the
d-dimensional lattice {1,2,… ,n^1/d}^d contains Θ (n^d+1) affine images of a cube. 



  
Our results.

We suppose we can perform exact computations over the reals.
Therefore, all the algorithms that we consider are either uniform algorithms in the real RAM model, or nonuniform algorithms in the algebraic decision tree model.

Our main result is the following.

  
  SIMILARITY MATCHING and AFFINE MATCHING reduce in randomized linear time to .
  

We refer the reader to the exact definitions of the  problem and the notion of randomized linear-time reduction given later.
Theorem <ref> has a number of consequences.
For instance, combining the reduction provided by Theorem <ref> with the real RAM algorithm for  from Chan <cit.>, we obtain the following.


  There exists an O((n^2/log n)(loglog n)^2) randomized real RAM algorithm for SIMILARITY MATCHING with a pattern size k=3.
  In particular, there exists a subquadratic algorithm to detect equilateral triangles in a point set.


This contrasts with our current knowledge on the related -hard problem of finding three collinear points, also known as GENERAL POSITION TESTING.
Despite recent attempts <cit.>, it is still an open problem to find a subquadratic algorithm for GENERAL POSITION TESTING.

Our next corollary is obtained directly from known algorithms for .
It improves on the best known O(n^d+1log n) algorithm whenever k<2(d+1).

  There exists an O(n^⌈ k/2⌉) (for k odd), or an O(n^k/2log n) (for k even) randomized real RAM algorithm for AFFINE MATCHING.


Finally, we consider the nonuniform decision tree complexity, also known as query complexity, of the two problems.
By applying a recent result of Kane, Lovett, and Moran <cit.>, we can bound the number of algebraic tests that are required to detect copies of P in an input set S.



There exist algebraic decision trees of height O(nlog^2 n) for SIMILARITY MATCHING and AFFINE MATCHING.


In fact, if the pattern P is a fixed parameter, that is, when P is not part of the input, but known at the algorithm design time, then the decision tree in the statement above only involves linear tests.



There exist linear decision trees of height O(nlog^2 n) for the fixed-parameter versions of SIMILARITY MATCHING and AFFINE MATCHING, in which P is a fixed parameter of the problems.


In the case k=3, SIMILARITY MATCHING is one of the two similarity testing problems recently tackled by Aronov, Ezra, and Sharir <cit.>.
They consider the problem of deciding, given three sets A,B,C of n points in the plane, whether there exists (a,b,c)∈ A× B× C that simultaneously satisfies two real polynomial equations.
They provide a subquadratic upper bound on the algebraic decision tree complexity of this problem.
We observe that SIMILARITY MATCHING with k=3 can be cast as such a problem in which the two equations are linear, and that in that case the decision tree complexity becomes near-linear. We therefore improve on one of the results of Corollary 4.4 in <cit.>.
A thorough discussion of the relation between the two problems and that of testing polynomials for vanishing on product point sets can be found in the full version of the paper <cit.>.



  
Plan. In the next section, we define a number of variants of the  problem and prove they are all equivalent in the computation model we consider. In Section <ref>, we prove our main result for SIMILARITY MATCHING. Section <ref> considers the AFFINE MATCHING problem. The last section is dedicated to the proof of Corollaries <ref> and <ref>.



§ LINEAR DEGENERACY TESTING



We first give a definition of the  problem.
Here, k≥ 3 is a fixed integer, and X is a ring. 

[X]
Given k sets A_1,… ,A_k of n elements of X, determine whether there exists a k-tuple a_1,… ,a_k∈_i=1^k A_i such that ∑_i=1^k a_i =0.


Our next problem is often referred to as linear degeneracy testing <cit.>.
We consider the cases where X=ℝ or ℂ with the usual addition and multiplication operations, or where X=ℝ^d or ℂ^d for some integer d≥ 2, with the vector addition and Hadamard (entrywise) product defined by (uv)_i = u_iv_i.
In the latter cases, the all-zero vector is denoted by 0, and the all-one vector by 1.

[X]
For a linear function f X^k→ X given by f(a_1,… ,a_k)= β_0 + ∑_i=1^k β_i a_i with β_i∈ X for 0≤ i≤ k,
given k sets A_1,… ,A_k of n elements of X, determine whether there exists a k-tuple a_1,… ,a_k∈_i=1^k A_i such that f(a_1,… ,a_k)=0.


We make two observations. First, these are fixed-parameter problems: the integer k is part of the definition of the problem, not of the input. The same can be assumed for the function f.
Such parameters will be referred to as fixed in what follows.
Another observation is that using the Hadamard product in the definition of the function f allows us to combine conditions on the sought k-tuples: In the ring X, searching for k-tuples that simultaneously satisfy d linear equations can be cast as X^d.

It is clear that  is the special case of  in which β_0=0 and β_i=1 for 1≤ i≤ k.
On the other hand,  is not harder than .


For any integer d>0, X reduces in linear time to X.


Consider the sets A_i from the  instance, and let A'_i {β_i a | a∈ A_i } for all 1≤ i< k, and A'_k{β_k a+β_0| a∈ A_k}.
Then the instance of  composed of the sets A'_i has a solution if and only if the instance of  has a solution.


In what follows, we say that a problem A reduces to problem B in randomized g(n) time
if there exists an algorithm in the real RAM model with access to random real numbers in [0,1] that 
maps any instance of size n of A to an equivalent instance of B in time O(g(n)) with probability 1.
If we insist on using only random bits, we can make the error probability arbitrary small by using sufficiently many random bits.

Over the reals, the vector and scalar versions of  are also essentially equivalent, up to such a randomized reduction.


For any fixed integer d>0, ℝ^d reduces in randomized linear time to ℝ .


Given an instance {A_1,… ,A_k} of ℝ^d, pick a uniform random unit vector v∈ℝ^d and 
consider the sets A'_i {a· v | a∈ A_i}⊂ℝ (here a· v is the usual dot product).
They form an instance of ℝ such that any solution to the original instance of ℝ^d is also a solution.
In the other direction, suppose there is a k-tuple a'_1,… ,a'_k∈_i=1^k A'_i such that ∑_i=1^k a'_i =0, where a'_i=a_i· v.
Hence we have ∑_i=1^k a_i· v=0, which is either because v⊥∑_i=1^k a_i and ∑_i=1^k a_i≠ 0, or because ∑_i=1^k a_i=0.
Since v⊥∑_i=1^k a_i and ∑_i=1^k a_i≠ 0 occurs with probability 0, the k-tuple a_1,… ,a_k is a solution of the instance 
{A_1,… ,A_k} of ℝ^d with probability 1.


We also make the following simple observation:



ℂ^d is equivalent to ℝ^2d.




§ SEARCHING FOR A SIMILAR COPY



We first consider the special case of the SIMILARITY MATCHING problem in which k=3.
[TRIANGLE]
Given a triangle Δ and a set S of n points in the plane, determine whether S contains three points whose convex hull is similar to Δ.


The short proof of the following result uses the interpretation of points in the plane as complex numbers, an idea that was exploited in a combinatorial context before <cit.>.

TRIANGLE reduces in linear time to ℂ.


Let u=re^iθ be such that the three numbers 0,1,u are the vertices of a triangle similar to Δ in the complex plane.
Recall that multiplying by re^iθ has a geometric interpretation in the complex plane as scaling by a factor r and rotating by an angle θ. 
Hence three other complex numbers a,b,c∈ℂ form a triangle similar to Δ in the complex plane with the same orientation if and only if c-a=u(b-a), or equivalently if (u-1)a-u b+c = 0.
Hence TRIANGLE reduces to ℂ with β = (u-1, -u, 1).
From Lemma <ref>, it reduces in linear time to ℂ.


Combining with Observation <ref> and Lemma <ref>, we obtain:

TRIANGLE reduces in randomized linear time to ℝ.


This generalizes naturally to larger patterns.

  
SIMILARITY MATCHING reduces in linear time to ℂ^k-2. 


Let u_1,… ,u_k-2∈ℂ be such that the set Q={0,1,u_1,… ,u_k-2} is similar to P in the complex plane.
Then k numbers a_1,… ,a_k∈ℂ form a similar copy of Q in the complex plane, with a_1 mapped to 0, a_2 to 1, and so on, if and only if a_i - a_1 = u_i-2 (a_2 - a_1) for all 3≤ i≤ k. 
These are k-2 linear equations on the k complex numbers a_1,… ,a_k, hence SIMILARITY MATCHING reduces in linear time to ℂ^k-2. 
From Lemma <ref>, it reduces in linear time to ℂ^k-2.


Again, combining with Observation <ref> and Lemma <ref>, we obtain the first statement of Theorem <ref>.

  
SIMILARITY MATCHING reduces in randomized linear time to ℝ.




§ SEARCHING FOR AN AFFINE IMAGE



We now prove the analogous result for the affine case.
As a warm-up, we first consider the following simpler special case of AFFINE MATCHING in which the pattern is a square.
Four points form the affine image of vertices of a square if and only if they are the vertices of a (possibly degenerate) parallelogram.
Hence the problem can be cast as follows.

[PARALLELOGRAM]
Given a set S of n points in the plane, determine whether S contains four points whose convex hull is a parallelogram.



PARALLELOGRAM reduces in randomized linear time to 4ℝ.


Four points a_1,a_2,a_3,a_4∈ S in this order form a parallelogram with a_1a_2 parallel to a_4a_3 and a_2a_3 parallel to a_1a_4 if and only if a_2-a_1 = a_3-a_4, or equivalently if a_1-a_2+a_3-a_4=0.
Hence PARALLELOGRAM reduces to 4ℝ^2 with β = ((0,0),(1,1),(-1,-1),(1,1),(-1,-1)).
From Lemmas <ref> and <ref>, it also reduces in randomized linear time to 4ℝ.


The general case follows from the following observation.
Consider a matrix Q∈ℝ^n× n, and let Q_k denote the matrix obtained from Q by replacing its kth column by the column vector x^T, where x_1, x_2,… ,x_n are variables.
Then Q_k is a linear combination of x_1, x_2,… ,x_n, with coefficients defined by Q.


  
AFFINE MATCHING reduces in linear time to ℝ^ℓ with ℓ =d(k-(d+1)).


We use the notation [k]{1,2,… ,k}.
Let p_i=(p_i,1,… ,p_i,d) be a row vector representing the ith point of P.
From the problem definition, P must contain d+1 affinely independent points.
We assume, without loss of generality, that these points are the first d+1 points p_1,… ,p_d+1.
Let A={a_1,… ,a_k}∈S k be a candidate match.
In order for the set A to be the image of P under an affine transformation, there must be a solution to the system of k linear equations of the form p_iF + t=a_i for all i∈ [k], with d^2+d real unknowns F∈ℝ^d× d and t∈ℝ^d.
The system can be decomposed into d systems, one for each coordinate j∈ [d].
Each consists of k equations with d+1 unknowns, of the form p_i F_j + t_j = a_ij for i∈ [k], where F_j is the jth column of F. 
We consider one such system, for a fixed j∈ [d], and restrict it to the first d+1 equations only:

    Q ·[ F_j; t_j ]
    =
    [   a_1,j;       ⋮; a_d+1,j ],
     where 
    Q=
    [   p_1     1;     ⋮     ⋮; p_d+1     1 ] .


Since the first d+1 points of P are affinely independent, Q is invertible and the system defines a unique solution for the coefficients F_j and t_j of the affine transformation.
From Cramer's rule, the value of the kth unknown is the ratio Q_k /  Q, where Q_k is the matrix 
obtained by replacing the kth column of Q by (a_1,j,… ,a_d+1,j)^T.
From the above observation and the fact that Q does not depend on S, the expressions Q_k /  Q are linear combinations of the values a_1,j,… ,a_d+1,j, with coefficients determined by P.
Hence the explicit solution for the coefficients F_j and t_j are linear combinations of the a_1,j,… ,a_d+1,j.

A necessary and sufficient condition for the set A to be a match is that the remaining k-d-1 points of A are also images of the corresponding points in P.
Hence we require that for all i>d+1 the ith equation
p_i F_j + t_j = a_ij is also satisfied by this solution.
The unknowns F_j and t_j can be replaced by linear combinations of a_1,j,… ,a_d+1,j.
Hence we obtain a set of k-(d+1) linear equations on the variables a_1,j,… ,a_k,j, with coefficients depending on P.

Since these k-(d+1) equations must hold for all coordinates j∈ [d] simultaneously, we obtain that 
AFFINE MATCHING reduces to ℝ^ℓ with ℓ =d(k-(d+1)).
From Lemma <ref> it also reduces to ℝ^ℓ.
Since d and k are fixed, the reduction takes linear time.


Combining with the randomization step in Lemma <ref>, we get the second part of Theorem <ref>.


  
  AFFINE MATCHING reduces in randomized linear time to ℝ.




§ ALGEBRAIC DECISION TREE COMPLEXITY


An algebraic decision tree is a type of nonuniform algorithm for problems on inputs composed of n real numbers.
For each input size n, it consists of a binary tree whose internal nodes are labeled with inequalities of the form “q(x)≤ 0” on the input x∈ℝ^n, where q is a bounded-degree n-variate polynomial in x_1,x_2,… ,x_n.
Inequalities are interpreted as queries on the input, and the two subtrees correspond to the possible outcomes of the query on the input.
Leaves of the tree are labeled with the answer to the problem.
The minimum height h(n) of an algebraic decision tree solving instances of size n the problem is the decision tree complexity, or query complexity of the problem.
When the queries only involve linear functions, such trees are called linear decision trees.
In that case, a query is said to be t-sparse when it involves at most t numbers of the input.

We have the following recent result on the linear decision tree complexity of the  problem.


  
The  problem on n elements can be solved by a linear decision tree of height O(nlog^2 n) in which
all the queries are 2k-sparse and have only {-1,0,1} coefficients.


We now show that this result directly applies to the SIMILARITY MATCHING and AFFINE MATCHING problems, thereby proving Corollary <ref>.

We first consider the SIMILARITY MATCHING problem, an instance y of which consists of two coordinates per point of P and S, hence of 2(k+n) real numbers.
Suppose we apply the reduction proposed in Theorem <ref> to obtain an instance of ℝ.
Now consider the linear decision tree from Theorem <ref>.
Each linear query on the transformed input maps to a query on the original input numbers y.
Because the reduction only involves multiplications and additions on these numbers, such queries are algebraic queries on the original input y.
Therefore, the linear decision tree for  maps to an algebraic decision tree of the same height for SIMILARITY MATCHING.
The same reasoning applies to AFFINE MATCHING.
In that case, it suffices to observe that multiplying both sides of every query by the quantity Q for the matrix Q used in the proof of Lemma <ref> yields algebraic queries again.
Note that since k and d are constant and the linear queries in Theorem <ref> are sparse, the queries have bounded degree and bounded size.
This proves Corollary <ref>.

Also note that if we suppose the pattern P is a fixed parameter of the problem, then the two problems are solved by linear decision trees of height O(nlog^2 n). It can indeed be checked that the algebraic queries do not involve multiplications between coordinates of the points of S, hence are linear whenever P is fixed. This proves Corollary <ref>.
It applies in particular to the PARALLELOGRAM problem, or for finding an equilateral triangle in a point set.

plain


