M7130 Geometric algorithms I

Faculty of Science
Autumn 2000
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
prof. RNDr. Jan Slovák, DrSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Contact Person: prof. RNDr. Jan Slovák, DrSc.
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
  • Mathematics (programme PřF, M-MA, specialization Discrete Mathematics)
  • Mathematics (programme PřF, N-MA, specialization Discrete Mathematics)
Course objectives (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 can also be completed outside the examination period.
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Autumn 2007 - for the purpose of the accreditation, Autumn 1999, Autumn 2010 - only for the accreditation, Autumn 2001, Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2011 - acreditation, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, autumn 2017, Autumn 2018.
  • Enrolment Statistics (Autumn 2000, recent)
  • Permalink: https://is.muni.cz/course/sci/autumn2000/M7130