کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657717 | 690091 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Random generation of Q-convex sets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Random generation of Q-convex sets Random generation of Q-convex sets](/preview/png/9657717.png)
چکیده انگلیسی
The problem of randomly generating Q-convex sets is considered. We present two generators. The first one uses the Q-convex hull of a set of random points in order to generate a Q-convex set included in the square [0,n)2. This generator is very simple, but is not uniform and its performance is quadratic in n. The second one exploits a coding of the salient points, which generalizes the coding of a border of polyominoes. It is uniform, and is based on the method by rejection. Experimentally, this algorithm works in linear time in the length of the word coding the salient points. Besides, concerning the enumeration problem, we determine an asymptotic formula for the number of Q-convex sets according to the size of the word coding the salient points in a special case, and in general only an experimental estimation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 393-414
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 393-414
نویسندگان
Sara Brunetti, Alain Daurat,