M013 Geometrické algoritmy I

Fakulta informatiky
podzim 1998
Rozsah
3/0. 3 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
Garance
Kontaktní osoba: prof. RNDr. Jan Slovák, DrSc.
Předpoklady
Je doporučeno absolvovat P009 Základy počítačové grafiky.
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
Osnova
  • Konvexní mnoúhelníky (průniky, incidence bodů, algoritmy pro konvexní obaly -- jednoprůchodový algoritmus, Grahamovo prohlížení, Jarvisův pochod, balení balíčku, algoritmy ve vyšších dimenzích).
  • Voronoiho diagramy a jejich aplikace (algoritmus metodou rozděl a panuj, zobecnění, aplikace, problém nejbližších sousedů, geometrické transformace).
  • 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 zjemňování).
  • Průniky (průniky úseček metodou pročesávání, průniky polorovin a konvexních mnohoúhelníků, aplikace a vícerozměrné algoritmy).
  • Vyhledávání podle rozsahu (multidimensionální binární stromy, metoda přímého přístupu, stromy úseček).
  • Úlohy o obdélnících (míra sjednocení obdélníků, obvod sjednocení mnohoúhelníků, průniky obdélníků).
Informace učitele
http://www.math.muni.cz/~slovak/#1
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 zima 1995, zima 1997, podzim 1999, podzim 2000, podzim 2001.