Pattern Matching for Sets of Segments

In this paper we present algorithms for a number of problems in geometric pattern matchingwhere the input consists of a collection of orthogonal segments in the plane. Such collections arise naturallyfrom problems in mapping buildings and robot exploration.We propose a new criterion for segment similarity called the coverage measure, and present efficientalgorithms for maximizing it between sets of axis-parallel segments under translations. In the general case,we present a procedure running in time O(n³ log² n), and for the case when all segments are horizontal, wegive a procedure that runs in time O(n² log² n). Here n is the number of segments. In addition, we showthat an -approximation to the Hausdorff distance between two sets of horizontal segments under verticaltranslations can be computed in time O(n^3/2 max(poly(log M, log n, 1/))). Here, M denotes the ratio of thediameter 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 timeO(n⁴ log²