Personal tools
You are here: Home CG seminar 2018 The RMS Partial-Matching Diagram
« January 2021 »
Log in

Forgot your password?

The RMS Partial-Matching Diagram

Wednesday, December 6th, 2017, 16:10

Schreiber 309


The RMS Partial-Matching Diagram

Geva Kipper, TAU


We discuss the problem of minimizing the RMS partial matching distance of point sets under translation, introduced by Rote in 2010, with applications in image pattern matching.
It is an open problem to compute the optimal translation in time that is polynomial in the sizes of the input point sets.
For the planar case, we suggest efficient polynomial-time algorithms for approximating the minimum distance up to a constant or ($1 + \epsilon$) factor, as well as algorithms that compute approximate partial matching diagrams.
We improve the best known exact algorithms by describing an algorithm that computes a single cell of the partial matching diagram in $O(nm^2 + nm \log n)$ time.
On the real line, we improve the running time of this algorithm further to $O(nm)$.
For the RMS proximity measure, we show that the known properties of the partial matching diagram do not suffice to give a polynomial upper bound on its complexity, by constructing an orthogonal subdivision with convex-span $k$ whose complexity is super-polynomial in $k$.
In case the RMS measure is replaced with any polyhedral norm, such as $L_1$ or $L_\infty$, we show a polynomial upper bound on the complexity of the resulting partial matching diagram.
Document Actions