M013 Geometric Algorithms I

Faculty of Informatics
Autumn 1999
Extent and Intensity
3/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: k (colloquium). Other types of completion: zk (examination), z (credit).
Teacher(s)
prof. RNDr. Jan Slovák, DrSc. (lecturer)
Guaranteed by
prof. RNDr. Jan Slovák, DrSc.
Departments – Faculty of Science
Contact Person: prof. RNDr. Jan Slovák, DrSc.
Prerequisites
M008 Algebra I
It is preferable to take P093 Computational Geometry Project at the same time. 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).
Literature
  • 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. and 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
Assessment methods (in Czech)
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 Computational Geometry Project.
Language of instruction
Czech
Further comments (probably available only in Czech)
Information on completion of the course: K ukončení zkouškou je nutné vypracovat projekt
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 1998, Autumn 2000, Autumn 2001.
  • Enrolment Statistics (Autumn 1999, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn1999/M013