Matching sets of line segments (Q2662685)

The authors study several versions of the line-segments matching problem. In this problem we have two sets of line segments \(S\) and \(S'\) and we search for a matching between them under a set of transformations \(F\). In the considered versions of the problem the authors use Hausdorff and bottleneck distances. In the third version we try to find the largest subset \(C \subset S\) such that there exists a transformation \(f \in F\) that matches \(C\) to a subset of \(S'\). The authors introduce approximation algorithms to solve these problems for various sets of transformations, i.e., translations in arbitrary dimension, rotations about a fixed point, rigid motions in two dimensions. The proposed approximation algorithms are about as efficient as the currently known algorithms for point-set pattern matching. The proposed algorithms first compute a discretization of the set of transformations and then solve the problem approximately for each transformation in this set using known algorithms. Namely, in the case of Hausdorff distance, the approximate near-neighbour data structure proposed in [\textit{S. Arya} et al., J. ACM 45, No. 6, 891--923 (1998; Zbl 1065.68650)] is used, and the geometric matching algorithm introduced in [\textit{A. Efrat} et al., Algorithmica 31, No. 1, 1--28 (2001; Zbl 0980.68101)] is used for the remaining two problems.