کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327368 | 680998 | 2015 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting triangulations and other crossing-free structures approximately
ترجمه فارسی عنوان
شمارش مثلث ها و دیگر ساختارهای بدون عبور از تقریبا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هندسه الگوریتمی، ساختارهای بدون عبور، الگوریتم شمارش، سه گانه الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in Oâ(2n) time [9], which is less than the lower bound of Ω(2.43n) on the number of triangulations of any point set [30]. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by Î the output of our algorithm and by cn the exact number of triangulations of P, for some positive constant c, we prove that cnâ¤Îâ¤cnâ
2o(n). This is the first algorithm that in sub-exponential time computes a (1+o(1))-approximation of the base of the number of triangulations, more precisely, câ¤Î1nâ¤(1+o(1))c. Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 5, July 2015, Pages 386-397
Journal: Computational Geometry - Volume 48, Issue 5, July 2015, Pages 386-397
نویسندگان
Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel,