پوشاننده های هندسی

اسلاید آن را قبلا گذاشته بودم. (اسلاید دانشگاه یزد بود).

الگوریتم حریصانه ی اصلی جواب بهینه را حساب می کند اما دومی که زمان کمتری می برد O(n^2 log n) جواب بهینه را حتی برای حالت متریک حساب نمی کند.

به جای این کار می خواهیم به صورت زیر عمل کنیم:

تتا-گراف:

انواع تتا گراف:

تتا گراف پوشای سینک:

تتاگرافی است که درجه ی آن محدود است.

پوشاننده ی لیست پرشی:

تتاگرافی که قطر آن از مرتبه لگاریتم تعداد راسهاست.

زمان آن O(n log n) است و حافظه O(n) است.