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

1- الف) یک چندضلعی با n راس و h حفره k راسی داریم. تعداد مثلثهای مثلث بندی آن چقدر است؟

ب) یک ذوزنقه بندی داریم که در آن پاره خط ها متقاطع هستند (مجزا نیستند)، تعداد ذوزنقه ها و مثلث ها چقدر است؟ (ناحیه ها)

ج) در یک kd tree حداکثر ناحیه هایی که یک خط آنها را قطع می کند چندتا است؟

د) یک مثال کلی و قابل تعمیم بزنید که نمی توان چند ضلعی دارای حفره را با floor(n/3) نگهبان (مساله art gallery) پوشش داد.

2- الف) چند ضلعی ستاره شکل (قبلا توی وبلاگ گفته شده)

ب) یک پیش پردازش روی آن انجام بدهید که زمان O(n) ببرد و در زمان O(logn) بتوان گفت هر نقطه در درون آن چندضلعی است یا بیرون.

3- range tree

الف) برای یک مستطیل با اضلاع موازی y=x و y=-x

ب) برای یک مثلث با دو ضلع موازی محورهای مختصات و یک ضلع موازی y=-x

ج) برای مجموعه n خط که بخواهیم برای سه تایی های (t0,t1,t2)، خطوطی را برگردانیم که بالای (1,t0) و زیر (t1,1) و (2,t2) باشند. (جای مختصاتها را برعکس می نویسد شما درستش را بخوانید!)