میان ترم هندسه محاسباتی شریف

سوال1: الف) تعداد یالهای تقاطع n خط n^2 است، تعداد یالهای تقاطع n صفحه چندتاست؟

ب) n نقطه و m خط داریم، تعداد تقاطع ها (نقطه های روی خطها) با عوض کردن تعداد نقطه ها و خط ها ثابت می ماند. (خودم دوگان گرفتم)

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

سوال 2: ثابت کنید اگه دو تا نقطه روی دایره بیرونی باشه، باید دو تا نقطه هم روی دایره توییه باشه، اگه بخوایم دو دایره ی هم مرکز حساب کنیم که همه ی نقاط بینشون بیفتن. با استفاده از دیاگرام ورونوی و دیاگرام ورونوی دورترین نقطه.

سوال 3: یه چند ضلعی ساده داریم، یه قطر اون رو پیدا کنید. توی O(n).

سوال 4: t تا مثلث داریم، دوگان اینها چی میشه؟ چطوری یه خطی پیدا کنیم که بیشترین تعداد مثلث رو قطع کنه؟

سوال 5: n تا دایره به شعاع یک داریم، در چه صورتی میشه از هر نقطه ی p به هر نقطه ی q رسید؟ (با عبور از اشتراک دایره ها) -- با EMST حل کردم.

سوال 6:  یه افراز از یه مربع می سازیم به این شکل که از پایین ترین نقطه شروع می کنیم یه خط به چپ راست و بالا رسم می کنیم. بعد برای نقطه های بالاتر به ترتیب این کار رو می کنیم. (منظور بر حسب y مرتب شده بودنه). 

الف) ثابت کنید این تعدادش O(n) میشه. (تعداد ناحیه ها)

ب) یه الگوریتم افزایشی برای به دست آوردنش بدید و زمان بدترین حالتش رو حساب کنید.

ج) ثابت کنید اگه رندم نقطه اضافه کنیم، متوسط تعداد به روز رسانی ناحیه ها O(1) میشه.