| Autor: |
Siu-Wing Cheng, Chi-Kit Lam |
| Rok vydání: |
2013 |
| Předmět: |
|
| Zdroj: |
Computational Geometry. 46:591-603 |
| ISSN: |
0925-7721 |
| Popis: |
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@?(n^2@e^-^3) time. The error is additive and it is at most @e@?min{area(P),area(Q)} with probability 1-n^-^O^(^1^). We also obtain an algorithm that approximately maximizes the overlap of P and Q under rigid motion in O@?(n^3@e^-^4) time. The same error bound holds with probability 1-n^-^O^(^1^). We also show how to improve the running time to O@?(n+@e^-^3) for the translation case when one of the polygons is convex. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect