ACM SCG slide 3

Algorithmic techniques are also represented, such as this monument to David Kirkpatrick's "optimal point location in a planar subdivision" in the Nitobe Japanese gardens.
David's method removes vertices of a planar graph to obtain a point location problem on a graph that is smaller by a multiplicative constant factor. (Note how the monument captures the fact that this constant is close to unity.)

David's work also appears off-campus: Bloedel conservatory illustrates the Dobkin-Kirpatrick hierarchy for polyhedra.

Next, Prev, Start, Home