کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414767 681033 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Shape matching under rigid motion
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Shape matching under rigid motion
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 6, August 2013, Pages 591–603
نویسندگان
, ,