روشی برای نمایش و محاسبه ی تعداد مثلث بندی های مجموعه ریوس در صفحه دو بعدی مبتنی بر کدگذاری

یک مثلث بندی T حاصل از مجموعه ریوس S در صفحه، برابر با بزرگترین گراف راست خط بر روی این مجموعه ریوساست، به گونه ای که گراف حاصل مسطح باشد. در این مقاله، هدف تبدیل مثلث بندی T حاصل از مجموعه ریوس S موجود در صفحه دو بعدی به یک رشته دودویی است که (w(T نامیده می شود. اگر n تعداد ریوس موجود در صفحه باشد، طول این رشته که با (f(n بیان میشود در محدوده ([(n-3)+2[3n/4] +≤f(n)≤ 4n-9 +f(n-1)(f([3n/4) قرار می گیرد. باتوجه به ویژگی اعداد دودویی تعداد مثلث بندی ها برابر (2f(n میباشد. همچنین در این مقاله نشان داده می شود که با داشتن یک رشته دودویی معتبر، ریوس موجود در صفحه و مجموعه فرض های در نظر گرفته شده می توان به یک مثلث بندی منحصر به فردی از مجموعه ریوس موجود در صفحه رسید.

کلیدواژه ها:

مجموعه ریوس ، مثلث بندی ، کدگذاری ، شمارش