Discrete Algorithmic Geometry

Discrete Algorithmic Geometry II

Time and Place:

First lecture on October 8, 1996.

Room: K 009D

Contents:

• Motivation and connection to other courses.
• Geometric Searching (point location, range search problems).
• Convex Hulls.
• Neighbourhood relationship (closest point problems, Voronoi Diagrams, Triangulations).
• Intersections (hidden-line/hidden-surface algorithms, intersection of polygons, polyhedra).
• Geometry of Rectangles.
• Arrangements of hyperplanes.
• Orientation of contours.
• Raytracing.

Relevant literature:

• Preparata/Shamos, `Computational Geometry'.
• Edelsbrunner, `Algorithms in Combinatorial Geometry'.