M7130 Geometrické algoritmy I

Přírodovědecká fakulta
podzim 1999
Rozsah
3/0/0. 5 kr. Ukončení: zk.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
Garance
prof. RNDr. Jan Slovák, DrSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Jan Slovák, DrSc.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
  • Matematika (program PřF, M-MA, směr Diskrétní matematika)
  • Matematika (program PřF, N-MA, směr Diskrétní matematika)
Osnova
  • 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ů)
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 2007 - akreditace, podzim 2010 - akreditace, podzim 2000, podzim 2001, podzim 2002, podzim 2003, podzim 2004, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018.