انجمن کامپیوتر ایران

مثلث‌بندي T با n رأس، m يال و f وجه در صفحه R^2را در نظر بگيريد. مسئله کدگذاري، مثلث‌بندي T را به رشته بيتي مانندS تبديل مي‌کند. هدف اين مسئله، ارائه روشي براي هر چه کوتاه‌تر ساختن رشته S همراه باقابليت بازسازي مثلث‌بندي از روي آن و حداقل پيچيدگي زماني الگوريتم‌هاي کدگذاري و کدگشايي است. در اين مقاله، يک روش کدگذاري براي مثلث‌بندي مجموعه نقاط داده شده در صفحه R^2 مطرح مي‌شود. اين روش کدگذاري، بر اساس توليد دوگان مثلث‌بندي و پيمايش DFS روي گراف دوگان طراحي‌شده است. الگوريتم کدگشايي يک الگوريتم بازگشتي است که قابليت بازسازي مثلث‌بندي از رشته S را دارد. با کمک اين روش مي‌توان طول رشته‌ي کد شده را به 4n-5 log⁡n-10+2n log⁡n بيت براي هر مثلث‌بندي داده شده، رساند که اين مقدار از کليه روش‌هاي ارائه شده تا به حال کمتر است.