Pattern matching for sets of segments

DOI10.1007/S00453-004-1089-YzbMATH Open1082.52008arXivcs/0009013OpenAlexW3137533644MaRDI QIDQ1762985FDOQ1762985

Authors: Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian 

Publication date: 11 February 2005

Published in: Algorithmica (Search for Journal in Brave)

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 emph{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}polylogn)$ in the general case, and run in time $O(n^{2}polylogn)$ 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}slpolylogn)$. These algorithms form significant improvements over the general algorithm of Chew et al. that takes time $O(n^{4}lo{g}^{2}n)$. In the second part of this paper we address the problem of matching polygonal chains. We study the well known Frd, and present the first algorithm for computing the Frd under general translations. Our methods also yield algorithms for computing a generalization of the Fr distance, and we also present a simple approximation algorithm for the Frd that runs in time $O(n^{2}polylogn)$.

Full work available at URL: https://arxiv.org/abs/cs/0009013

Recommendations

• Pattern matching for sets of segments
• Geometric pattern matching for point sets in the plane under similarity transformations
• Matching sets of line segments
• Matching sets of line segments
• Approximate matching of polygonal shapes

zbMATH Keywords

Computational geometryPattern matchingMaximum coverageOrthogonal segments

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Artificial intelligence for robotics (68T40)

Cited In (7)

• Set intersection and sequence matching with mismatch counting
• The manipulability of matching rules via segmentation
• Matching sets of line segments
• Approximately matching polygonal curves with respect to the Fréchet distance
• Pattern matching for sets of segments
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Pattern matching for sets of segments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1762985)