کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868528 | 1439978 | 2018 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A fast algorithm for computing irreducible triangulations of closed surfaces in Ed
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We give a fast algorithm for computing an irreducible triangulation Tâ² of an oriented, connected, boundaryless, and compact surface S in Ed from any given triangulation T of S. If the genus g of S is positive, then our algorithm takes O(g2+gn) time to obtain Tâ², where n is the number of triangles of T. Otherwise, Tâ² is obtained in linear time in n. While the latter upper bound is optimal, the former upper bound improves upon the currently best known upper bound by a lgâ¡n/g factor. In both cases, the memory space required by our algorithm is in Î(n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 68, March 2018, Pages 327-357
Journal: Computational Geometry - Volume 68, March 2018, Pages 327-357
نویسندگان
Suneeta Ramaswami, Marcelo Siqueira,