Abstract
In this paper we present algorithms for a number of problems in geometric pattern matching where the input consists of a collection of orthogonal segments in the plane. Such collections arise naturally from problems in mapping buildings and robot exploration. We propose a new criterion for segment similarity called the coverage measure, and present efficient algorithms for maximizing it between sets of axis-parallel segments under translations. In the general case, we present a procedure running in time O(n3 log 2 n), and for the case when all segments are horizontal, we give a procedure that runs in time O(n2 log2 n). Here n is the number of segments. In addition, we show that an ε-approximation to the Hausdorff distance between two sets of horizontal segments under vertical translations can be computed in time O(n3/2 max(poly(log M, log n, 1/ε))). Here, M denotes the ratio of the diameter to the closest pair of points in the sets of segments (where pairs of points lie on different segments). These algorithms are significant improvements over the general algorithm of Agarwal et al. that required time O(n4 log2.
Original language | English (US) |
---|---|
Pages (from-to) | 147-160 |
Number of pages | 14 |
Journal | Algorithmica (New York) |
Volume | 40 |
Issue number | 3 |
DOIs | |
State | Published - Aug 2004 |
Keywords
- Computational geometry
- Maximum coverage
- Orthogonal segments
- Pattern matching
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics