Úloha 1 (Barevné body): V rovině je dána množina červených a množina zelených bodů. Sestrojte přímku, která obě množiny oddělí (nebo řekněte, že to nelze). Na jedné její straně tedy budou ležet všechny červené body, zatímco na druhé všechny zelené.

Úloha 2 (Dva ploty*): Mějme $n$ jabloní, které chceme uchránit oplocením. Všimněte si, že pokud bychom netrvali na tom, aby byly oplocené jedním plotem, mohli bychom ušetřit pletivo. Sestrojte dva uzavřené ploty tak, aby každá jabloň byla oplocena a celkově jste spotřebovali nejméně pletiva.

Nebojte se vysokého exponentu ve složitosti. Cokoliv polynomiálního je dobré.

Úloha 3 (Třídění): Představme si, že máme blackbox (podproceduru), která pro zadanou množinu bodů v rovině najde body na jejím konvexním obalu a vydá je seřazené podle pořadí, v jakém se na hranici konvexního obalu nacházejí.

Ukažte, že s pomocí takové podprocedury můžeme třídit obecná čísla (a tedy takový algoritmus na hledání konvexní obálky tak nejspíš nepůjde udělat v lepším čase než $\O(n \log n)$).

Úloha 4 (Dynamický konvexní obal*): Vymyslete datovou strukturu, která bude udržovat konvexní obal množiny bodů a bude ho umět rychle přepočítat po přidání bodu do množiny.

Úloha 5 (Obecná poloha): Náš algoritmus na hledání průsečíků úseček od zadaných úseček očekával následující čtyři pravidla „obecné polohy“. Vymyslete, jak algoritmus upravit, aby je očekávat nemusel.

1. Žádné tři úsečky nesdílí společný bod.
2. Průnikem každých dvou úseček je nejvýš jeden bod (zde domyslete, co bychom vlastně mohli chtít vypisovat, pokud pravidlo neplatí).
3. Krajní bod žádné úsečky neleží na jiné úsečce.
4. Neexistují vodorovné úsečky.

Úloha 6 (Průsečíky): Ukažte příklad $n$ úseček v „obecné poloze“ (podle předchozí definice), které mají $\Theta(n^2)$ průsečíků.

Úloha 7 (Obecnější Voroného diagram): Voroného diagram množiny bodů $M$ je rovinný graf (kde povolujeme hrany nekonečné délky), jehož každá stěna obsahuje právě body ležící blíže k některému bodu v $M$, než ke všem ostatním.

Jak by to dopadlo, kdyby prvky $M$ nebyly pouze body, ale mohly by to být i úsečky? Dokažte, že v takovém případě diagram opět tvoří rovinné nakreslení grafu, ovšem jeho hrany nemusí být pouze úsečky a (polo)přímky. Jak ještě můžou hrany vypadat?