Date:           Mon, 4 Nov 1996 19:09:41 +0100
From:           Rolf Klein <Rolf.Klein@FernUni-Hagen.de>
To:             Jeff Erickson <jeffe@cs.duke.edu>
Cc:             Rolf.Klein@FernUni-Hagen.de
Subject:        Re: "Algorithmische Geometrie"

On Nov 1, 10:55am, Jeff Erickson wrote:

Bernd Gärnter tells me that you have a new computational geometry textbook coming out. Can you give me some information about it to include in my computational geometry books page? All I know for sure is the title and that it's written in German.
Thanks!
- Jeff

Hi Jeff,

thanks for your interest! Yes, the book is in German and will probably come out in December 96 (Addison-Wesley, 390 pages). It is based on a graduate course I wrote at the FernUniversität Hagen, the only remote university of Germany; so I've tried to keep it self-contained and suitable for self-studying. There are about 90 exercises with solutions. Undergraduates can read it after their basic course on data structures and analysis.

Below is a short table of contents.

Best regards,

Rolf

prerequisites (a little about topology, graphs, elementary geometry, computational model, big-O, lower bounds)
sweep (maximum subvector, closest pair in 2D, line segment intersection, lower envelope, Davenport-Schinzel- sequences)
geometric data structures (range tree, k-d-tree, priority search tree; classical general dynamization techniques for amortized and worst case)
intersections and visibility (2D convex hull: randomized incremental + worst case; visibility polygon, visibility decomposition, art gallery; kernel of a polygon: after Cole & Goodrich)
distance problems (planar Voronoi diagram and Delaunay triangulation: structural properties and applications; generalization to convex distance functions, to line segments)
computing Voronoi diagrams (randomized incremental, sweep, divide&conquer, geometric transformation)
motion planning under uncertainty (escaping from a labyrinth: Pledge algorithm; finding a goal: Bug, doubling; searching for the kernel: CAB)