Date:           Mon, 4 Nov 1996 19:09:41 +0100
From:           Rolf Klein <>
To:             Jeff Erickson <>
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.

- 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,


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