Abstract
In this paper we present algorithms for a number of problems in geometric pattern matching where the input consist of a collections of segments in the plane. Our work consists of two main parts. In the first, we address problems and measures that relate to collections of orthogonal line segments in the plane. Such collections arise naturally from problems in mapping buildings and robot exploration. We propose a new measure of segment similarity called a coverage measure, and present efficient algorithms for maximising this measure between sets of axis-parallel segments under translations. Our algorithms run in time $O(n^3 \text{polylog } n)$ in the general case, and run in time $O(n^2 \text{polylog } n)$ for the case when all segments are horizontal. In addition, we show that when restricted to translations that are only vertical, the Hausdorff distance between two sets of horizontal segments can be computed in time roughly $O(n^{3/2} \text{polylog } n)$. These algorithms form significant improvements over the general algorithm of Chew et al. that takes time $O(n^4 \log^2 n)$. In the second part of this paper we address the problem of matching polygonal chains. We study the well known Fréchet distance, and present the first algorithm for computing the Fréchet distance under general translations. Our methods also yield algorithms for computing a generalization of the Fréchet distance, and we also present a simple approximation algorithm for the Fréchet distance that runs in time $O(n^2 \text{polylog } n)$.
Introduction: The Challenge of Geometric Alignment
Geometric pattern matching is the fundamental task of determining the optimal alignment between two sets of shapes. While the Hausdorff distance—the maximum distance from any point in one set to the nearest point in another—is a standard metric, it often fails in practical applications like robotics. It is "blind" to the continuity of shapes, treating a solid wall and a sparse cloud of points identically. This paper addresses two critical domains where standard metrics fall short: robot mapping of orthogonal environments and the matching of continuous polygonal chains.
Robots exploring indoor environments typically generate maps composed of horizontal and vertical line segments representing walls. Aligning these scans is difficult because sensors often capture only partial segments or introduce noise. Furthermore, for trajectory matching, the Fréchet distance—often visualized as the minimum leash length required for a man to walk his dog along two separate paths—is the preferred metric. However, computing this distance while allowing for arbitrary translation to find the "best fit" remained an open algorithmic challenge.
Algorithmic Methods
1. The Coverage Measure for Orthogonal Segments
To overcome the limitations of the Hausdorff distance, the authors introduce the coverage measure. This metric calculates the total length of segments in one set that are "covered" by segments in another set within a specified distance $\epsilon$. This approach is inherently more robust to outliers and partial data.
The paper utilizes a sweep-line algorithm that traverses the translation plane. By employing dynamic data structures like segment trees, the authors maintain the maximum coverage efficiently as the sweep-line encounters segment endpoints. For the specific case of horizontal segments undergoing vertical translation, the problem is reduced to a variation of interval matching, solvable using Fast Fourier Transforms (FFTs) to find optimal alignment.
2. Fréchet Distance under Translation
The core of the Fréchet distance computation lies in the "free space diagram," which maps all pairs of points on two curves that are within distance $\epsilon$ of each other.
To solve this under translation, the authors identify "critical events" where the topology of the free space changes. By representing the free space as a directed acyclic graph (DAG) and using advanced data structures like "cuttings" to maintain reachability information, they provide the first exact algorithm for Fréchet distance under general translation.
Key Results and Insights
The research provides significant improvements over existing complexity bounds:
- Axis-Parallel Efficiency: By leveraging the orthogonal nature of architectural environments, the authors reduced the complexity of matching from $O(n^4)$ to $O(n^3 \log^2 n)$, or even $O(n^2 \log n)$ for purely horizontal segments.
- Hausdorff Breakthrough: For horizontal segments under vertical translation, the complexity was improved to $O(n^{3/2} \text{polylog } n)$.
- Fréchet Translation: The paper presents the first algorithm for Fréchet distance under general translation with a complexity of $O(n^{10} \text{polylog } n)$. While theoretically high, it establishes a baseline for a previously unsolved problem.
- Practical Approximation: A faster $O(n^2 \text{poly}(\log n, 1/\beta))$ approximation algorithm is provided for applications where a near-optimal solution is sufficient.
Conclusion and Future Work
This work demonstrates that structural assumptions, such as axis-parallelism, can lead to dramatic algorithmic speedups in spatial pattern matching. While the $O(n^{10})$ complexity for the Fréchet distance is primarily of theoretical interest, it paves the way for more efficient future implementations. Current limitations include the focus on 2D translation; future research could integrate rotation into the Fréchet distance algorithms or extend these measures to 3D wireframe models.
Summary updated