هسته با روش دو برابر کردن (جویباری)

*روش دو برابر کردن معمولی

تقریب عرض جهتی:

دو نقطه‌ی اول را s و t می‌نامیم. هر بار یک نقطه جدید می‌آید (p) عرض این سه نقطه را حساب می‌کنیم و اگر نقطه جدید از دو برابر نقطه قبلی دورتر بود نقطه جدید را جایگزین قبلی می‌کنیم.

اثبات آن مشابه اثبات الگوریتمی است که دورترین نقطه از یک نقطه را می‌گرفت و سپس دورترین نقطه را از این پاره‌خط به دست می‌آورد. (تقریب ۳) به جز این از نامساوی مثلث استفاده شده است. هر بار به دلیل دوبرابر کردن تقریب نصف می‌شود پس یک تصاعد هندسی با ضریب ۱/۲ داریم.

*روش قبل را با استفاده از توری و دیاگرام ورونوی گسسته حل می‌کنیم. (مینیمم و ماکسیمم نقاط را نگه می‌داریم.)

در ادامه مقاله ایده‌ی الگوریتم ترکیبی قطر (رند کردن جهتی و توری) هم آمده که با دیاگرام ورونوی گسسته برای محاسبه دورترین نقطه به زمان بهتری برای قطر رسیده است.

با استفاده از این روش یک راه کلی ساختن هسته ارائه داده است که یک الگوریتم افزایشی روی تعداد ابعاد است (مثل دیاگرام ورونوی گسسته)‌ که هر بار با استفاده از توری نقاط را روی راستای دورترین دو نقطه تصویر می‌کند. (یعنی قطر فعلی). حداکثر میزان تغییرات مثل قبل به دلیل نصف شدن محدود است.

*بهبود الگوریتم با روش merge and reduce

(با روش رند کردن جهتی اپسیلون-کرنل ساخته می‌شود.)