Name
Abstract | ||
|---|---|---|
The problem of computing a largest common point set (LCP) between two point sets under Ɛ-congruence with the bottleneck matching metric has recently been a subject of extensive study. Although polynomial time solutions are known for the planar case and for restricted sets of transformations and metrics (like translations and the Hausdorff-metric under L∞-norm), no complexity results are formally known for the general problem. In this paper we give polynomial time algorithms for this problem under different classes of transformations and metrics for any fixed dimension, and establish NP-hardness for unbounded dimensions. Any solution to this (or related) problem, especially in higher dimensions, is generally believed to involve implementation difficulties because they rely on the computation of intersections between algebraic surfaces. We show that (contrary to intuitive expectations) this problem can be solved under a rational arithmetic model in a straightforward manner if the set of transformations is extended to general affine transformations under the L∞-norm (difficulty of this problem is generally expected to be in the order: translations |
Year | Venue | Keywords |
|---|---|---|
2000 | ESA | restricted set,general problem,complexity result,largest common point set,computing largest common point,different class,point set,polynomial time algorithm,approximate congruence,polynomial time solution,algebraic surface,general affine transformation |
Field | DocType | ISBN |
Affine transformation,Discrete mathematics,Combinatorics,Computer science,Computational geometry,Isometry,Algebraic surface,Time complexity,Cylindrical algebraic decomposition,Congruence (geometry),Pattern matching | Conference | 3-540-41004-X |
Citations | PageRank | References |
22 | 1.55 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Samarjit Chakraborty | 2 | 1840 | 185.70 |
| Bernd Gärtner | 3 | 461 | 45.50 |