Computational Geometry

Lecturer:

Tutor:

Supervisor:

Department of Computer Graphics and Interaction

Synopsis:

Principles of computational geometry (CG), data structures and paradigms, methods of geometric search, convex polygons and hulls, applications of convex hull, proximity problems, Voronoi diagrams, triangulation, efficient intersection algorithms, intersection of semispaces and polygonal regions, geometry of rectangles, dual mappings and spaces, convex hull in dual space, algorithms of computer graphics and CG.

Requirements:

Students are required to solve semestral project.

Syllabus of lectures:

1. Computational geometry (CG), typical applications, effective algorithm design techniques

2. Geometric searching

3. Geometric searching 2

4. Planar convex hull

5. Convex hull in 3D

6. Proximity problems, Voronoi diagram.

7. Voronoi diagram applications.

8. 2D a 3D triangulations

9. Intersections of line segments

10. Intersections of polygonal areas and halfspaces

11. Geometry of parallelopids.

12. Dual algorithms.

13. Spare lecture

Syllabus of tutorials:

1. Assignment of topics for individual presentations

2. Representation of Planar graph, search trees

3. Interval search, BSP trees

4. Searching in planar subdivision

5. Convex hull in 2D

6. Convex hull in 3D. Diameter of a point set.

7. Construction of higher order Voronoi diagram( VD). Generalization of VD

8. Proximity problems solved by the Voronoi diagram

9. Delaunay triangulation and minimal weight triangulation

10. Application of triangulations, stratification of the triangulation.

11. Algebra of polygonal areas. Searching of the polygon core.

12. Construction of the boundary of unified rectangles, intersection of rectangles.

13. Crediting

Study Objective:

The course is an informal continuation of fundamental data structures and algorithms courses. You will learn geometric algorithms and data structures allowing for effective computations, e.g., localization of area hit by a ray, computation of intersections and triangulation. You will train presentation and professional discussion skills on the seminars. All of it should not be missing in knowledge of educated progressive Master of Science.

Study materials:

1. de Berg, M.,van Kreveld, M., Overmars, M., Schvarzkopf, O.: Computational Geometry, Berlin, Springer, 1997.

2. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

3. Edelsbrunner H.: Algorithms in Combinatorial Geometry. Berlin, Springer - Verlag, 1987.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: