تمرین های فصل 1 کتاب هندسه har peled

1- فرض کنید C و P دو مجموعه از نقاط در صفحه باشند، طوری که |C| = k و |P|=n.

r=max_p_in_P min_c_in_C ||c-p||

قرار دهید r را شعاع پوشا برای P توسط C. (یعنی اگر یک دایره به شعاع r حول هر کدام از نقاط C قرار دهیم این دایره ها همه ی نقاط P را می پوشانند.)

الف) یک الگوریتم با زمان اجرای متوسط O(n+k log n) بدهید که عدد a را برگرداند که a <= r <= 10a. {یک 10 تقریب از شعاع پوشا}

ب) برای هر epsilon >0 که در ورودی داده می شود، یک الگوریتم با زمان متوسط O(n+k/epsilon^2 log n) بدهید که عدد a را برگرداند که a <= r <= (1+epsilon)a باشد.

2- مجموعه P از n نقطه در صفحه و پارامتر k داده شده است. یک الگوریتم تصادفی ساده بدهید که در زمان متوسط O(n (n/k)) یک دایره شامل k نقطه از P برگرداند که شعاع آن کمتر از 2 برابر شعاع بهینه ی پوشاندن k نقطه از P باشد.

-----------------------------------------------------------------------------------------------------

حل:

1- ایده: الگوریتم تصادفی افزایشی، توری تطبیق دهنده، مشابه سوال نزدیک ترین زوج نقاط

(هر بار از جواب مرحله قبل برای ساختن توری جدید استفاده می کنیم. اگر نقطه جدید درون خانه ی شامل یک عضو از C افتاد که جواب تغییر نمی کند و در غیر این صورت جواب با زمان O(k) قابل محاسبه است. احتمال تغییر جواب هم مثل قبل 1/i است که i شماره ی مرحله یا به عبارت دیگر تعداد نقاط اضافه شده از مجموعه ی P است.)

2- حل قبلی که برای این مساله داده شد با زمان O(n (n/k)^2) بود و ایده ی آن استفاده از توری غیریکنواخت بود و یک الگوریتم قطعی بود. با ترتیب تصادفی نقاط تقاطع توری را چک می کنیم و هر بار از مینیمم r (شعاع دایره شامل k نقطه) به دست آمده برای چک کردن دایره بعد استفاده می کنیم: تعداد نقاط خانه های مجاور را که فاصله ی کمتری از شعاع فعلی دارند بررسی می کنیم اگر کمتر بود جواب تغییر نمی کند.