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