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

منبع: 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).

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