Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

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

Highlights
Master Server