محاسبه کوچکترین توپ محیطی
شنبه, ۲۳ فروردين ۱۳۹۳، ۰۱:۲۱ ب.ظ
*روش افزایشی
هر بار یک نقطه را اضافه میکنیم و توپ محیطی را حساب میکنیم تا شامل همه نقاط شود. این کار را با استفاده از این نکته که هر نقطه جدید حتما روی محیط میافتد انجام میدهیم.
حالا باید ضریب تقریب آن را به دست بیاوریم. دایره جواب بهینه را در نظر میگیریم. فاصلهی مرکز دایره i-ام تا نقطه i-ام برابر شعاع دایره i-ام است و اگر آن را امتداد دهیم قسمت دیگر حداکثر سه برابر این قسمت است. میدانیم طول وتر از قطر کمتر است پس از اینجا ضریب تقریب ۳/۲ به دست میآید.
؟؟ چرا سه نقطهی pi,ci,c(i-1) همخط اند؟
*روش تکراری
یک نقطه دلخواه بر میداریم و به مجموعه Q اضافه میکنیم. دایره محیطی Q را به دست میآوریم و دورترین نقطه به آن از بین نقاط اولیه (به مرکز دایره) را به Q اضافه میکنیم و این کار را ادامه میدهیم تا توپ شامل همهی نقاط شود.
۹۳/۰۱/۲۳