Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1202.68447
Aiger, Dror; Kedem, Klara
Geometric pattern matching for point sets in the plane under similarity transformations. (English)
[J] Inf. Process. Lett. 109, No. 16, 935-940 (2009). ISSN 0020-0190

Summary: We consider the following geometric pattern matching problem: Given two sets of points in the plane, $P$ and $Q$, and some (arbitrary) $\delta >0$, find a similarity transformation $T$ (translation, rotation and scale) such that $h(T(P),Q)<\delta $, where $h(\dot ,\dot )$ is the directional Hausdorff distance with $L_{\infty }$ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, $\delta $ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set $Q$. If the $L_{\infty }$ distance between every pair of points in $Q$ is at least $8\delta $, then the problem can be solved in $O(mn^{2} \log n)$ time, where $m$ and $n$ are the numbers of points in $P$ and $Q$ respectively. If the $L_{\infty }$ distance between every pair of points in $Q$ is at least $c\delta $, for some $c, 0<c<1$, we present a randomized approximate solution with expected runtime $O(n^{2}c^{-4}\epsilon ^{-8}\log ^{4}mn)$, where $\epsilon >0$ controls the approximation. Our approximation is on the size of the subset, $B \subset P$, such that $h(T(B),Q)<\delta $ and $|B|>(1 - \epsilon )|P|$ with high probability.

MSC 2000:: *68U05 Computational geometry, etc.
68W25 Approximation algorithms
68W20 Randomized algorithms
68T10 Pattern recognition
68P10 Searching and sorting

Keywords: approximation algorithms; randomized algorithms; computational geometry; geometric pattern matching; Hausdorff distance

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]