Applied
Computational Geometry

Prof.dr.ing.Ivana Kolingerová

http://afrodita.zcu.cz/~kolinger

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.

**Lectures:**

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

**References:**

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