Applied Computational Geometry Kolingerová


Department of Computer Science and Engineering

Faculty of Applied Sciences

University of West Bohemia in Pilsen


Input knowledge: necesseary: data structures, algorithmisation, programming in any programmimg language, recommended: basic knowledge of computer graphics – on the level of a basic course.



1.      Computational geometry as a tool for geometric and graphical applications

2.      Geometric search - point location, range search

3.      Convex hulls in 2D, 3D

4.      Voronoi diagrams - properties, construction

5.      Voronoi diagrams - generalizations and applications

6.      Planar triangulations (Delaunay, greedy, data dependent, constrained, minimum weight, multicriterially optimized) and their applications

7.      Tetrahedronizations and their applications

8.      Polygon triangulation and decomposition (into trapezoids, convex polygons), art gallery problem

9.      Medial axis

10.  Surface reconstruction from scattered points

11.  Intersections (line segments, polygons, halfplanes, dualities)

12.  In case of interest and free time: scientific writing, presentations, creativity




1. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1st edition, 1994 or 2nd edition, 2000

2. de Berg, Mark, van Kreveld, Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms and Applications, Springer Verlag, 1st edition, 1997 or 2nd edition, 2001

3. Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985

4. PowerPoint presentation files on the course home page and other materials provided by the teacher in the printed form


Seminars: The main point is analysis and presentation of existing algorithms and design of new ones.



Requirements :


Main possibilities to get points for the total evaluation are as follows:


1. To solve a set of smaller problems until the required number of points is collected. The solved tasks are namely oriented to the design of algorithms (usually without impementation), writing of essays from some given literature, algorithmic presentation, implementation of smaller geometrically oriented problems. The tasks will be handed out within the whole semester and they have a relation to the course topics.


2. One bigger task comprising a design of solution, implementation, testing, written description and conclusions for some more difficult problem to collect the required number of points. The topic will be given by the agreement of the teacher and the student and will have some relation to the course topics. Together with agreement with the handout the teacher will state how many points for what level of task fulfillment will be given. The topic can be further extended into the diploma work in the case of interest of both parties.


3. Active participation in the seminars and solution of some homework tasks.


The presented forms can be freely combined; it is your choice how much and which work you will do to get the required amount of points.


For the exam a thorough knowledge of the lecture, excercises and hand-out-problems solutions are required. Recommended literature 1 should be known briefly. The main is to be able to reason and apply the lectured algorithms to a particular problem, to be able to choose the most proper method for the given data. The exam is written and oral, in the written part there are three questions or problems to solve, the oral part is mainly devoted to the analysis of the student’s work and his/her written exam.



Minimal required amount of points to get credits: 30 for a standard fulfillment of the semestra work. The extra, above-standard amount of points is unlimited and depends on the student’s diligence.


Maximal possible amount of points at the exam: 30 for 3 questions per 10 points. If less then the exam is to be repreated.


The whole evalution:

If you pass the exam, the sum of exam and seminar points are added as follows:


 61 points and more  -  excellent

 51 – 60 points          - very good

 45 – 50 points          - good

 less points                - failed