کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9654916 | 680905 | 2005 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Enumerating pseudo-triangulations in the plane
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A pseudo-triangle is a simple polygon with exactly three convex vertices. A pseudo-triangulation of a finite point set S in the plane is a partition of the convex hull of S into interior disjoint pseudo-triangles whose vertices are points of S. A pointed pseudo-triangulation is one which has the least number of pseudo-triangles. We study the graph G whose vertices represent the pointed pseudo-triangulations and whose edges represent flips. We present an algorithm for enumerating pointed pseudo-triangulations in O(logn) time per pseudo-triangulation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 30, Issue 3, March 2005, Pages 207-222
Journal: Computational Geometry - Volume 30, Issue 3, March 2005, Pages 207-222
نویسندگان
Sergey Bereg,