سوال هندسه محاسباتی

مرجع: تمرین های http://www.cs.uu.nl/docs/vakken/ga

تمرین 1:

1- مجموعه ای از n پاره خط مجزا و m دایره ی غیر متقاطع (می توانند متداخل باشند) داده شده است. همه ی دایره هایی که هیچ پاره خطی را قطع نمی کنند گزارش دهید. (راهنمایی: sweep)

هر دایره را به 2 قسمت بالا و پایین تقسیم می کنیم. بعد می توانیم مثل پاره خط در نظر بگیریم، چون در sweep فقط این مهم است که نسبت به قبل جای آنها جا به جا شده باشد. بقیه اش مثل قبل است.

تمرین 1: (شانس دوم!)

1- الف) چندضلعی ساده ی P داده شده است که تنها یک راس turn دارد (merge,split,start,end). یک الگوریتم O(n) ارائه دهید که آن را مثلث بندی کند.

(برای تعریف راس turn به sweep مربوط به مثلث بندی که در پست های قبلی موجود است نگاه کنید.)

ب) ثابت کنید که هر چندضلعی ساده که O(1) راس مقعر داشته باشد، O(1) راس turn دارد.