E-learning to the course

 

Sources for English e-learning

Book on computational geometry

Algorithms for convex hull in the plane

Covex sets, convex hull od a set, convex hull of a set of n points. Naive algorithm for convex hull. Efficient algorithm (Graham Scan) with running time O(n log n). Lexicographic ordering of points, upper and lůower convex hull. How to expess mathematically  "right turn". Pseudocode. Gift Wrepping algorithm.

Xerox staršího vydání knihy je po jednotlivých kapitolách k dostání v Marečkově knihkupectví.

References for the 1st lecture

Blackboards

Algorithm for intersections of segments

For given set of segments the algorithm finds all intersections, moreover to every intersections gives all segments on which it lies. The algorithm is based on so called "sweep line method". Its time complexity is  O((n+k) log n), where n jis the number of segments and k the number of intersections. 

 

References

Blackboards

Diploma thesis Map Overlap and Segment Intersections by Dominik Janků (in Czech)

Algorithm for finding the overlap of two planar subdivisions

Description of planar subdivisions by doubly connected edge list.

Algorithm has two steps. In the first one we make modifiocation of tables for vertices and edges using speep line method. In the second spet we look for faces of the overlap using cycles of edges. Moreover, to every face of the overlap we find the faces of original maps in which the face lies.
Time complexity is O(n log n+k log n), where n is the complexity of the input and k is the complexity of the output.

Application. Intersection and union of two polygons.

Blackboards

Diploma thesis Map Overlap and Segment Intersection by  Dominik Janků (in Czech)

Triangulace mnohoúhelníků - rozdělení nekonvexního jednoduchého mnohoúhelníka na monotónní části

Art gallery problem: rozmístit v galerii tvaru nekonvexního mnohoúhelníka co nejmenší počet kamer, které mohou sledovat celou galerii. Matematická formulace: triangulace nekonvexního jednoduchého mnohoúhelníka a obarvení vrcholů třemi barvami tak, že v každém trojúhelníku jsou všechny barvy.

Algoritmus triangulace má dva kroky - rozdělení nekonvexního jednoduchého mnohoúhelníka na monotónní části a triangulaci monotónních částí. Definice monotónního mnohoúhelníka, typy vrcholů start, end, regular, split, merge. Mnohoúhelník je monotónní, právě když nemá vrcholy typu split a merge. Idea - pomocí diagonál směrem dolů likvidovat vrcholy typu split a pomocí diagonál nahoru likvidovat vrcholy typu merge.

Rozdělení na monotónní části. Sweep line algoritmus, události jsou vrcholy mnohoúhelníka. Vyvážený binární strom popisuje pořadí úseček protínajících zametací přímku a majících mnohoúhelník vpravo. Důležitý pojem "helper". Podle typu vrcholů -start, end, regular, split, merge - vedeme nové diagonály, měníme strom a helpery. Časová náročnost O(n log n), kde n je počet vrcholů.

Blackboards

Průnik n polorovin hledáme metodou rozděl a panuj. Ten vede na hledání průniku dvou mnohoúhelníkových konvexních oblastí. Popis těchto oblastí pomocí  levé a pravé hranice. Metoda zametací přímky. Události jsou vrcholy a v průběhu algoritmu spočítané průsečíky hranic. Hledáme vrcholy a hrany na levé a pravé hranici průniku. Potřebný čas je O(n log n).

 

Blackboards

Formulace problému, možná řešení - prázdný průnik (infeasible), má řešení (feasible), neomezený lineární program ve směru vektoru c. Přírustkový algoritmus, lemma o nalezení bodu maxima, řešení jednodimenziálního problému v lineárním čase.

 

Blackboards

Detailed description of the algorithm (in Czech)

Motivace, vhodné deatové struktury jsou kd-stromy a range-trees. 1-dimenzionální vyhledávání. Vyvážený binární strom, v něm hledáme všechy listy ležící v intervalu [x,x`]. Split vrchol, algoritmy FIND SPLIT NODE a 1D RANGE QUERY. Vybudování stromu O(nlog n), vyhledávání O(log n+k), kde k je počet vyhledaných bodů, paměť O(n).

kd-stromy

Které body z dané množiny leží v obdélníku [x,x`]x[y,y`]. Konstrukce kd-stromu, geometrická motivace, algoritmus BUILD kd-TREE (P, depth). Čas konstrukce O(nlog n), paměť O(n).Region uzlu, algoritmus SEARCH kd-TREE typu rozděl a panuj, rekurentní formule pro vyhledávací čas dává čas vyhledání O(n^1/2+k). Odstranění zjednodušujících předpokladů na souřadnice bodů z množiny P vede k lexikografickému uspořádání.

Blackboards

Motivace, lichoběžníková mapa, počet vrcholů i lichoběžníků lineární podle počtu úseček, popis lichoběžníků, levý, pravý horní a dolní soused. Vyhledávací struktura D, orientovaný graf bez cyklů s lichoběžníky v listech, uzly typu x a y, předpoklady na souřadnice, algoritmus TRAPESOIDAL MAP na straně 28. Podrobněji o jednotlivých krocích algoritmu TRAPESOIDAL MAP. Vyhledání lichoběžníku, ve kterém leží levý bod přidávané úsečky, vyhledání lichoběžníků, které jsou novou úsečkou protínány - algoritmus FOLLOW SEGMENT na straně 29. Aktualizace lichoběžníkové mapy. Aktualizace vyhledávací struktury.  (Detaily v práci O. Folvarčného.)  Odstranění předpokladů na y-nové souřadnice vrcholů úseček pomocí shear transformation a lexikografického uspořádání v uzlech typu x. Odvození očekávaného času vyhledávání O(log n), očekávané velikosti vyhledávací struktury O(n) a očekávaného času její konstrukce O(n log n).

Blackboards

Diagramy Voronoia

Motivace - post office problem. Matematicky: pro danou množinu P bodů v rovině najít podrozdělení roviny na oblasti tvořené body, které mají nejblíže k danému bodu množiny P. Výsledné podrozdělení se nazývá digramem Voronoia. Odhad na počet vrcholů a hran tohoto digramu. Charakterizace hran a vrcholů diagramu Voronoia pomocí kružnic. Algoritmus konstrukce pomocí pročesávací přímky. Beach line tvořená oblouky parabol. Kdy v beach line vzniká nový oblouk - site event. Kdy v beach line nějaký oblouk zaniká-circle event (kruhová událost). 

Datová struktura: fronta událostí (site a circle events), kruhové události jsou do fronty doplňovány až v průběhu algoritmu. Vyvážený binární strom T uchovává pořadí oblouků parabol. K každém listu je případný odkaz na kruhový bod, kdy oblouk zanikne. Algoritmy V-DIAGRAM, HANDLE SITE EVENT a HANDLE CIRCLE EVENT


 

Blackboards

Blackboards

Delaunayova triangulace 

Pojmy: úhlově optimální triangulace, legální triangulace, Delaunayův graf a Delaunayova triangulace.
Náhodný přírůstkový algoritmus, vše ve vhodném trojúhelníku p-2, p-1, p0. Vyhledávací struktura D - acyklický orientovaný graf.Algoritmy DELAUNAYOVA TRIANGULACE a LEGALIZUJ HRANU. Změny ve vyhledávací strukture. Volba bodů počátečního trojúhelníka. Očekávaný čas konstrukce je O(n log n), ocekavané požadavky na paměť O(n).

 

Blackboards

The exam is only written. It has three tasks. In two of them I ask you to describe an algorithm from the lectures. The third task is usually a set of questions concerning other algorithms or important notions from the course (doubly connected edge list, Euler Formula, mean value of random variable) or simple mathematical proofs.
I want you to give understandable description of basic idea, define exactly used notions and structures and be able to put down pseudocodes.
 

The exam lasts 2 hours. Here you are an example: