PřF:M7130 Geometric algorithms I

M7130 Geometric algorithms I

Faculty of Science
Autumn 1999

Extent and Intensity

3/0/0. 5 credit(s). Type of Completion: zk (examination).

Teacher(s)

prof. RNDr. Jan Slovák, DrSc. (lecturer)

Guaranteed by

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

Syllabus (in Czech)

Přehled tzv. "Computational Geometry". 1.Úlohy o konvexních mnoúhelnících (průniky, incidence bodů). 2.Algoritmy pro konvexní obaly (jednoprůchodový algoritmus, Grahamovo prohlížení, Jarvisův pochod, balení balíčku). 3.Voronoiho diagramy a jejich aplikace (algoritmus metodou rozděl a panuj, zobecnění, aplikace, problém nejbližších sousedů, geometrické transformace). 4.Triangulace a vyhledávání v rovinných rozděleních (Delaunayova triangulace, "lakomecká" triangulace, postupné triangulování s předem zadanými hranami, geometrické vyhledávání, metoda pásů, metoda cest, redukované vyhledávací struktury, metoda postupného zjemnování). 5. Průniky a podobné problémy (průniky úseček metodou pročesávání, aplikace a vícerozměrné algoritmy). 6.Vyhledávání podle rozsahů (multidimensionální binární stromy, metoda přímého přístupu, stromy úseček). 7.Úlohy o obdélnících (míra sjednocení obdélníků, obvod sjednocení mnohoúhelníků, průniky obdélníků)

Language of instruction

Czech

Further Comments

The course is taught annually.
The course is taught: every week.