M013 Geometric Algorithms I

Faculty of Informatics
Autumn 1998
Extent and Intensity
3/0. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Jan Slovák, DrSc. (lecturer)
Guaranteed by
Contact Person: prof. RNDr. Jan Slovák, DrSc.
Prerequisites
Before enrolling this course the students should go through P009 Principles of Computer Graphics.
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
  • Convex polygons (intersections, incidence, convex hulls --- Graham scan, Jarvis march, gift wrapping, algorithms in higher dimensions).
  • Voronoi diagrams and applications (divide and conquer algorithm, generalizations and diagrams of higher orders, applications, the nearest neighbor problem, use of geometric transformations).
  • Triangulations and searching in plane partitions (Delaunay triangulation, the greedy triangulation, the problem with some given edges, geometric searching, the strip method, the method of pathes, reduced search structures, the method of iterative refinement).
  • Intersections (intersection of segments --- the sweep paradigm, intersection of half-planes and convex polygons, aplications and higher dimensional algorithms).
  • Range searching (multidimensional binary trees, the direct access method, segment trees).
  • Iso-orthogonal objects (the area and the circumference of a union of rectangulars, intersections).
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
Teacher's information
http://www.math.muni.cz/~slovak/#1
The course is also listed under the following terms Autumn 1995, Autumn 1997, Autumn 1999, Autumn 2000, Autumn 2001.
  • Enrolment Statistics (Autumn 1998, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn1998/M013