تمرین های کتاب - فصل جستجوی بازه ها (درخت های هندسی)

جواب:

الگوریتم:

1- تصویر بازه ها روی محور x را حساب می کنیم و یک درخت بازه روی آن می سازیم. (interval tree)

2- در هر نود درخت بازه ی ساخته شده، یک درخت محدوده (range tree) روی تصویر پاره خطها روی محور y (یک نقطه به ازای هر پاره خط) می سازیم.

3- کوئری را اول روی درخت بازه جواب می دهیم بعد روی درخت محدوده ی آن.

اثبات درستی:

در قدم اول [x,x'] را پیدا می کنیم و در قدم دوم بازه ی y را هم چک می کنیم.

زمان، پیش پردازش، کوئری:

برای درخت بازه ها: تعداد پاره خط ها = تعداد پاره خط های ورودی = n

برای درخت محدوده: تعداد نقاط = تعداد پاره خط های ورودی = n

درختهای هندسی (ادامه)

تفاوت range tree و interval tree در این است که در range tree ما یک سری نقطه داریم و می خواهیم نقاط درون این بازه را به دست بیاوریم، اما در interval tree در درخت بازه ها را نگه می داریم و می خواهیم بازه های شامل نقطه ی داده شده را پیدا کنیم. در پیاده سازی کاری که می کنیم این است که در interval tree یک درخت روی نقاط سر بازه ها می سازیم، اما در range tree روی نقاط درخت می سازیم.

سوال دیگری که مانده بود این بود که ارتباط segment tree و range tree چیست. (دو بعدی)

در segment tree ما از ریشه که به سمت برگها می رویم، در طول مسیر بازه ها را گزارش می کنیم (شکل سمت راست) اما در range tree ما جایی که دو مسیر جدا می شوند زیر درخت های راست سمت چپی و چپ سمت راستی را گزارش می کنیم. (از این نظر فرقی بین range tree و interval tree نیست)

کاربردها و انواع segment tree

1- پیدا کردن بازه های شامل یک نقطه: segment tree معمولی

2- پیدا کردن مساحت مستطیل ها (اجتماع بازه ها): semi static segment tree

3- پیدا کردن پاره خطهای متقاطع با یک پاره خط عمودی: augmented segment tree

(در هر گره یک BST نگهداری می کنیم که ترتیب خطهای عمودی را نگه می دارد. شبیه کاری که در سوئیپ می کردیم)

4- پیدا کردن مستطیل های شامل یک نقطه: multi-level segment tree

 segment tree دو بعدی

Delauney vs. Delaunay

Voronoi Diagrams and Delauney triangulations are data structures to reason about points and regions in space...
... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.

http://www.cse.wustl.edu/~pless/546/

تمرینهای هندسه

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew1-2013-her.pdf

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew2-2013.pdf

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew2-2013-her.pdf

جواب تکلیف 2:

1- ham sandwich cut : دوگان نقاط را حساب می کنیم. خط جدا کننده خطی است که مثلا نقاط قرمز بالای آن و نقاط آبی زیر آن هستند. در فضای دوگان می شود نقطه ای که بین LE نقاط قرمز UE نقاط آبی باشد. (اگر همدیگر را قطع کنند.)

 *الآن به این نتیجه رسیدم که باید سوالهای حل کردنی (نه اثباتی) رو بخونم چون احتمالا تو امتحان از اینها میاد.

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

سوالهای کتاب:

4.11 Give an example of a 2-dimensional linear program that is bounded, but where there is no lexicographically smallest solution.

هر LP که جواب نداشته باشد.

4.9 Suppose we want to find all optimal solutions to a 3-dimensional linear program with n constraints. Argue that Ω(nlogn) is a lower bound for the worst-case time complexity of any algorithm solving this problem.

تصویر آن روی دو بعد CH است که بهتر از nlogn نمی توان حل کرد. (reduction)

6.1 Draw the graph of the search structure D for the set of segments depicted in the margin, for some insertion order of the segments.

6.2 Give an example of a set of n line segments with an order on them that makes the algorithm create a search structure of size Θ(n2) and worst-case query time Θ(n).

همان شکل سوال بالا.

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

مرجع: تمرین های 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 دارد.

6th Winter School On Computational Geometry February 19-24, 2014

برای من که فایده ای نداره، چون نهایتا سر کلاس یاد نمی گیرم چیز زیادی... بعدم احتمالا با ترم بعد تداخل داره ساعت کلاسهاش.

http://wscg.aut.ac.ir/wscg6/index.php?option=com_content&view=article&id=3&Itemid=2

6th winter school time table

	9:00-10:30	10:30-11:00	11:00-12:30
Feb. 19	Partiotion trees: The basics by Mark de Berg	Coffee break	Computing similarity between two curves by Joachim Gudmundsson
Feb. 20	Partition trees: trade-offs and multi-level structures  by Mark de Berg		Curve/trajectory clustering by Joachim Gudmundsson
Feb. 21	Partition trees: applications by Mark de Berg		Approximating the Frechet distance by Joachim Gudmundsson
Feb. 22	No Lecture
Feb. 23	Locally correct Frechet matching by Joachim Gudmundsson	Coffee break	Arrangements: upper envelopes, single cells and other substructures by Mark de Berg
Feb. 24	Curve segmentation by Joachim Gudmundsson		Arrangements: applications by Mark de Berg

محاسبه مساحت مستطیل های موازی محورهای مختصات با segment tree

مساله به klee's rectangle problem معروف است و راه حل توسط Bentley ارائه شده است.

یک sweep عمودی انجام می دهیم و هر بار اجتماع بازه هایی که داخل مستطیل ها هستند (xشان) را حساب می کنیم. (با segment tree)

این را در اختلاف y این مرحله sweep با مرحله ی قبل ضرب می کنیم و جمع اینها در کل sweep میشه جواب.

کاربردهای line arrangement

مثلث بندی چند ضلعی monotone