کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414727 | 681016 | 2014 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Flip distance between triangulations of a planar point set is APX-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set S in the Euclidean plane and two triangulations T1T1 and T2T2 of S , it is an APX-hard problem to minimize the number of edge flips to transform T1T1 to T2T2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 589–604
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 589–604
نویسندگان
Alexander Pilz,