Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414767 | Computational Geometry | 2013 | 13 Pages |
Abstract
We present improved algorithms to match two polygonal shapes P and Q to approximate their maximum overlap. Let n be their total number of vertices. Our first algorithm finds a translation that approximately maximizes the overlap area of P and Q under translation in O˜(n2ε−3) time. The error is additive and it is at most ε⋅min{area(P),area(Q)}ε⋅min{area(P),area(Q)} with probability 1−n−O(1)1−n−O(1). We also obtain an algorithm that approximately maximizes the overlap of P and Q under rigid motion in O˜(n3ε−4) time. The same error bound holds with probability 1−n−O(1)1−n−O(1). We also show how to improve the running time to O˜(n+ε−3) for the translation case when one of the polygons is convex.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Siu-Wing Cheng, Chi-Kit Lam,