کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868502 | 1439978 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The dual diameter of triangulations
ترجمه فارسی عنوان
قطر دوگانه سه گانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سه گانه، نمودار دوگانه، قطر، بهینه سازی، چند ضلعی ساده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let P be a simple polygon with n vertices. The dual graphTâ of a triangulation T of P is the graph whose vertices correspond to the bounded faces of T and whose edges connect those faces of T that share an edge. We consider triangulations of P that minimize or maximize the diameter of their dual graph. We show that both triangulations can be constructed in O(n3logâ¡n) time using dynamic programming. If P is convex, we show that any minimizing triangulation has dual diameter exactly 2â
âlog2â¡(n/3)â or 2â
âlog2â¡(n/3)ââ1, depending on n. Trivially, in this case any maximizing triangulation has dual diameter nâ2. Furthermore, we investigate the relationship between the dual diameter and the number of ears (triangles with exactly two edges incident to the boundary of P) in a triangulation. For convex P, we show that there is always a triangulation that simultaneously minimizes the dual diameter and maximizes the number of ears. In contrast, we give examples of general simple polygons where every triangulation that maximizes the number of ears has dual diameter that is quadratic in the minimum possible value. We also consider the case of point sets in general position in the plane. We show that for any such set of n points there are triangulations with dual diameter in O(logâ¡n) and in Ω(n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 243-252
Journal: Computational Geometry - Volume 68, March 2018, Pages 243-252
نویسندگان
Matias Korman, Stefan Langerman, Wolfgang Mulzer, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber,