Matching sets of line segments
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.
- Matching sets of line segments
- Approximate input sensitive algorithms for point pattern matching
- Pattern matching for sets of segments
- A simple algorithm for approximate partial point set pattern matching under rigid motion
- Combinatorial Pattern Matching
- Improved approximation bounds for planar point pattern matching
- Algorithms and Data Structures
- Matching Shapes with a Reference Point
- Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Approximate decision algorithms for point set congruence
- Approximate matching of polygonal shapes
- Approximating the maximum overlap of polygons under translation
- Congruence, similarity, and symmetries of geometric objects
- Finding Largest Common Point Sets
- Generalized Selection and Ranking: Sorted Matrices
- Geometric optimization and sums of algebraic functions
- Geometric pattern matching under Euclidean motion
- Geometry helps in bottleneck matching and related problems
- scientific article; zbMATH DE number 1424291 (Why is no real title available?)
- Maximizing the area of overlap of two unions of disks under rigid motion
- Maximizing the overlap of two planar convex sets under rigid motions
- The complexity of selection and ranking in X+Y and matrices with sorted columns
This page was built for publication: Matching sets of line segments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662685)
