کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331426 | 686693 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graham triangulations and triangulations with a center are hamiltonean
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let P be a point set with n elements in general position. A triangulation T of P is a set of triangles with disjoint interiors such that their union is the convex hull of P, no triangle contains an element of P in its interior, and the vertices of the triangles of T are points of P. Given T we define a graph G(T) whose vertices are the triangles of T, two of which are adjacent if they share an edge. We say that T is hamiltonean if G(T) has a hamiltonean path. We prove that the triangulations produced by Graham's Scan are hamiltonean. Furthermore we prove that any triangulation T of a point set which has a point adjacent to all the points in P (a center of T) is hamiltonean.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 93, Issue 6, 31 March 2005, Pages 295-299
Journal: Information Processing Letters - Volume 93, Issue 6, 31 March 2005, Pages 295-299
نویسندگان
Ruy Fabila Monroy, J. Urrutia,