Pattern matching for sets of segments

Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)147-160
Number of pages14
JournalAlgorithmica (New York)
Volume40
Issue number3
DOIs
StatePublished - Aug 2004

Keywords

  • Computational geometry
  • Maximum coverage
  • Orthogonal segments
  • Pattern matching

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Pattern matching for sets of segments'. Together they form a unique fingerprint.

Cite this