پایان ترم هندسه محاسباتی

(مال یه دانشگاه دیگه است)

خودش: http://www.cs.iastate.edu/~cs518/exams/final.pdf

جوابش: http://www.cs.iastate.edu/~cs518/exams/final-soln.pdf

خب به سبک همیشه اول من حل می کنم بعد چک می کنم.

قبلش یه چیزی در مورد سوالهای قبلی (میان ترم) بگم اونم اینکه تو سوال گالری با n/3 نگهبان حداکثر میشه کاری کرد که همه ی شکل دیده بشه و با سه رنگ کردن میشه همچین چیزی رو به دست آورد. (میشه مینیمم تعداد راسهایی که یک رنگ هستند.). اثباتش هم این طوری بود که مثلث بندی می کرد می گفت تو هر مثلث یه نگهبان باشه حلله. اثبات اینکه میشه مثلث بندی کرد هم با این گفته که دوگان گراف رو می کشیم، (برای دوگان کشیدن اون وجه بیرونی رو راس نگرفته)، بعد گفته دوگانش یه درخته با حداکثر درجه ی 3، چون اگه یکی رو حذف کنیم ناهمبند میشه. آخرشم با استقرا رنگش کرده.

http://www.cs.wustl.edu/~pless/546/lectures/l6.html

خب حالا برگردیم به حل سوالا. (آخرش نفهمیدم این مثلث بندی دوگانش اون وجه بیرونی رو میخواد یا نه!+چقدر دردناکه آدم جواب تمرینهایی که با بدبختی حل کرده بعدا پیدا کنه تو اینترنت! :|)

1- الف) هر چند ضلعی با y یکنوا رو میشه تو زمان خطی مثلث بندی کرد. درسته، چون همه اش رو میشه به اون راس اولیه وصل کرد مثلث ساخت.

ب) هر گره داخلی به جز ریشه توی kd-tree یک ناحیه مستطیلی موازی یک محور رو مشخص می کنه.

kd-tree یه درخته که هر عمقش یکی از محورهای مختصات در فضای d بعدی رو نصف می کنه. (به درد پیدا کردن نقطه ای می خوره که اول داشتیم بعد گم کردیم! :)) ) یعنی هر عمقی که میگذره یه بار نصف میشه، حالا بعد از بار اولی که نصف شد یه چیزی شبیه مستطیل میشه دیگه. (بیشتر مکعب مستطیل) چون کلا بازه اش محدوده. فکر کنم درسته. (ما که نخوندیم!) -غلطه انگار بازه اش محدود نیست اونی که بازه اش محدوده درخت بازه است.. :))

ج) درسته. یال غیر مجاز یعنی چی؟ :))

د) هر گراف دلانی هر دایره که یک یال قطرشه هیچ نقطه ای (از مجموعه نقاط ورودی) توش نیست. درسته، اصلا تعریف یال همینه. نمی دونم چرا غلطه! :| آهان: توی ورونوی یالها دایره ی خالی اند. توی دلانی یالها فقط نقاط رو به هم وصل می کنن. مثلا یه مثلث یه نقطه وسطش دایره ای که روی ضلع می سازی اون نقطه هه میفته توش. اگه دایره محیطی سه تا نقطه رو بکشی هیچی نمیفته توش.

ه) وقتی الگوریتم خط جاروی fortune رو اجرا می کنیم تا دیاگرام ورونوی رو بسازیم، هر کمانی روی خط ساحلی با یک نقطه ی متفاوت تعریف میشه. غلطه، چون هر نقطه یه سهمی میسازه، که می تونه چند بار توی خط ساحلی بیاد.

و) تعداد یالهای دیاگرام ورونوی با تعداد یالهای مثلث بندی دلانی مساویه. (برای یه مجموعه نقطه) درسته، چون هر یالی بین دو تا فیس ه و هر راس توی یه فیسه، وقتی دوگان می گیریم، هر فیس میشه یه راس و بین دو تا راس یه یاله. (مثال نقض: 4 نقطه روی یک دایره)

ز) حساب کردن تقاطع n تا نیم صفحه، از نظر محاسبه معادل ساختن CH نقاط دوگان خطوط مرزی این صفحه هاست. درسته،

2- یه درخت بازه برای مجموعه ی n تا بازه ... حافظه می گیره و می تونه بازه ی شامل یه نقطه رو در زمان ... بده. فقط دومی رو میدونم که logn میشه. دومی هم logn+k میشه! اولی n میشه.

3- با چه شرایطی arrangement مربوط به n تا خط ماکسیمم تعداد راس، یال و فیس رو داره؟

احتمالا وقتی همه خطها همدیگه رو قطع کنن! (این کافی نیست انگار: باید هیچ سه تایی هم توی یه نقطه قطع نکنند!)

4- نمی دونم منظورش اینه که جایی که می بینه بکشم یا جایی که میتونه ازش رد بشه. (منظورش این بوده که اگه حرکت کنه چه جاهایی رو نمیبینه!)

5- خوشبختانه/بدبختانه نخوندیم!

6- الف) CH نقاط S رو کشیدم بعد از رو مرزش رد شدم. (مرز بالایی نزدیک تر بود!)

ب) خب اگه منظورش مثل قسمت الف باشه که اگه r و s رو مستقیم وصل کردیم و CH مربوط به S رو قطع نکرد که حلله، وگرنه به CH مماس می کنیم و بعد از اون نقطه همین حرکت رو ادامه میدیم. (کلا دو تا مماس میشه این دو تا مسیر رو چک می کنیم.)

7-دوگان: مجموعه خطوط دوگان نقطه های خط l: y=mx+b چی میشه؟

میشه یه دسته خط به مرکز m,-b که اشتراکشون یه نقطه m,-b است. (یعنی اگه کل خط رو بخوایم میشه اشتراک اونها میشه یه نقطه، اگه تک تک نقطه ها رو بخوایم میشه یه سری خط که از یه نقطه میگذرن) -- خودش که ثابت کرده گذاشته توی رابطه اش در آورده، ولی قضیه اینه که این دسته خطی که گفتم یه خط (خط عمودی) رو کم داره!

8- مثلث بندی دلانی (دقت کنید شماره سوالا رو دارم اشتباه می زنم :)) نمی دونم از کجا اشتباه شده ولی دیگه دیره!)

یکی یکی باید نقطه اضافه کنیم و با اون locally Delaney درستش کنیم. از p به سه تا راس مثلثی که توش افتاده (1) وصل می کنیم بعد یال مثلثهای زیری p و 2 و بعد مثلث جدیده با 3 فلیپ میشن. -- ساختمان داده اش انگار این طوریه که تا برگ که بری اون ناحیه رو میده.. درست نفهمیدم و نخوندیم دیگه! :)

9- دیاگرام ورونوی:

الف) ثابت کنید بزرگترین دایره ی خالی که مرکزش توی CH نقاطه روی راس دیاگرام ورونوی میفته. (راهنمایی: برهان خلف)

فرض خلف: p درون یکی از سلول های دیاگرام ورونوی می افتد یا روی یک یال به جز در راس. اگر در یال بیفتد فاصله ی آن از دو نقطه (سابت) متناظر آن یال مساوی است و چون خالی است شعاع دایره از این فاصله کمتر مساوی است. هر چه دایره از محل تقاطع عمودمنصف سایتها با یال دور شود دایره بزرگتر می شود، پس چون در راس قطع نکرده یک دایره ی بزرگتر بوده است. در حالتی که درون یکی از ناحیه ها بیفتد، چون می دانیم در هر سایت فقط یک نقطه است پس  فاصله ی مرکز دایره تا آن نقطه از شعاع کمتر مساوی بوده است، پس فاصله ی مرکز دایره تا نقاط دیگر هم از شعاع دایره بیشتر بوده است، یعنی می توانستیم دایره ی بزرگتری بسازیم.

ب) ثابت کنید اگر روی CH باشد (برخلاف قسمت الف) باید روی یال دیاگرام ورونوی بیفتند.

خودش الف رو گفته فقط دایره رو میشه بزرگتر کرد تا از نقطه های دیگه هم بگذره، برای ب گفته که میشه به سمت راس حرکت داد. (من هر دو رو توی الف گفتم!)

ج) یک الگوریتم بدهید که این بزرگترین دایره را به دست بیاورد. زمان اجرای الگوریتم =؟

خودش گفته یه sweep با الگوریتم fortune بریم و VD بسازیم.

خب بعدش احتمالا باید راسهای این دیاگرام رو تست کنیم تا اونی رو پیدا کنیم که بزرگتره. فقط حالت ب رو چیکار باید کرد؟؟ روی تقاطع CH و ورونوی رو چک کرده..

البته اون قسمتی که از روی ورونوی CH ساخته نفهمیدم (گفته یه ناحیه باز پیدا کنید و ccw حرکت کنید) ولی خب در بدترین حالت میشه جدا حساب کرد.

الآن فهمیدم که CH نقاط سایت رو ساخته، از ورونوی هم برای این استفاده کرده که یه نقطه بیفته توش و جهت رو داشته باشه. بعدش گفته که نصف فاصله ی ضلع CH تا راس ورونوی رو تست کنید برای شعاع دایره.