کوچکترین توپ محیطی با روش مرکزهای متحرک
(مقاله دکتر ضرابی زاده)
حالتی که در پست قبلی در این مورد نوشته بودم به این دلیل در تحلیل آمده است که بدترین حالت مسأله است و بدیهی است که همیشه برقرار نیست.
در شکل بالا همیشه اگر از p3 به نقطه مماس وصل کنیم، چون شعاع در نقطه تماس بر خط مماس عمود است اگر از c1 بگذرد از c2 هم میگذرد. در غیر این صورت یک نقطهی دیگر روی محیط دایره دوم باید باشد تا این دایره کوچکترین دایره محیطی باشد. (حالت دو سر قطر اتفاق نمیافتد.)
این حالتی است که در آن دایره در هر مرحله (اضافه شدن هر نقطه) بزرگتر میشود، یعنی همیشه حالتی اتفاق میافتد که نقاط دو سر قطر دایره محیطی هستند. فقط میماند اثبات اینکه این بدترین حالت است.
جوابی که این الگوریتم میدهد ۳/۲-تقریبی است برای کوچکترین دایره محیطی نقاط و خود الگوریتم هم به این صورت است که به جای اینکه نقطه جدید و نقاط قبلی را در نظر بگیرد نقطه جدید و دایره محیطی قبلی را در نظر میگیرد و کوچکترین توپ محیطی آن را حساب میکند.