M013 Geometrické algoritmy I

Fakulta informatiky
podzim 1999
Rozsah
3/0. 3 kr. (plus ukončení). Doporučované ukončení: k. Jiná možná ukončení: zk, z.
Vyučující
prof. RNDr. Jan Slovák, DrSc. (přednášející)
Garance
prof. RNDr. Jan Slovák, DrSc.
Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Jan Slovák, DrSc.
Předpoklady
M008 Algebra I
Doporučuje se zapsat zároveň P093 Projekt z geometrických algoritmů. Je výhodné před zapsáním 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ů).
Literatura
  • O'ROURKE, Joseph. Computational geometry in C. 2nd ed. Cambridge: Cambridge University Press, 1998, xiii, 376. ISBN 0-521-64976-5. info
  • PREPARATA, Franco P. a Michael Ian SHAMOS. Computational geometry : an introduction. New York: Springer-Verlag, 1985, 398 s. ISBN 0387961313. info
  • Handbook of discrete and computational geometry. Edited by Jacob E. Goodman - Joseph O'Rourke. Boca Raton: CRC Press, 1997, xvi, 991 s. ISBN 0-8493-8524-5. info
Metody hodnocení
Výuka probíhá standardní formou. Doporučené ukončení je kolokvium, které probíhá formou jednoho písemného testu ve zkouškovém období po ukončení výuky. Ke zkoušce je třeba vypracovat praktický projekt a absolvovat po projití kolokviálním testem ještě ústní rozpravu. Lze přitom využít projekt vypracovaný v rámci P093 Projekt z geometrických algoritmů.
Informace učitele
http://www.math.muni.cz/~slovak/#1
Další komentáře
Poznámka k ukončení předmětu: K ukončení zkouškou je nutné vypracovat projekt
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 1998, podzim 2000, podzim 2001.