Computational Geometry

Lecturer:

Tutor:

Supervisor:

Department of Computer Science and Engineering

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. Subject of computational geometry ( CG )

2. Data structures and paradigms in CG

3. Methods of Geometric searching

4. Convex hulls and convex polygones

5. Applications of convex hull

6. Proximity problem

7. Voronoi diagram

8. Triangulation of polygons

9. Intersections of segments and lines

10. Intersection of semispaces and polygonal regions

11. Geometry of rectangles

12. Dual mappings and spaces, convex hull in dual space

13. Algorithms of computer graphics & computational geometry

14. Application of CG in Geographics Information Systems

Syllabus of tutorials:

1. Algorithms of generation and searching 2D-interval trees

2. Location of a point in a planar subdivision

3. Overmans's and van Leeuwen's algorithms for dynamic construction ofconvex hull

4. Covex hall in 3D

5. Construction of Voronoi diagram

6. Proximity problems solved by the Voronoi diagram

7. Algorithms of intersections of line segments

8. Algebra of plane polygons

9. Algebra of rectangles

10. Dual mappings, Line and plane intersections in a dual space

11. Presentation of student's projects

12. Presentation of student's projects

13. Presentation of student's projects

14. Crediting

Study Objective:

Study materials:

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

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

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

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Computer Technology - Computer Graphics- structured studies (compulsory course of the branch)