FI:M013 Geometric Algorithms I - Course Information

M013 Geometric Algorithms I

Faculty of Informatics
Autumn 1997

Extent and Intensity

2/1. 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

Teacher's information

http://www.math.muni.cz/~slovak/#1

The course is also listed under the following terms Autumn 1995, Autumn 1998, Autumn 1999, Autumn 2000, Autumn 2001.