18 Voronoi diagrams are generally useful, beyond proteins

• Voronoi polyhedra are used a wide variety of disciplines
  • Nearest neighbor problems. The nearest neighbor of a query point is center of the Voronoi diagram in which it resides
  • Largest empty circle in a collection of points has center at a Voronoi vertex
  • Voronoi volume of "something" often is a useful weighting factor. This fact can be used, for instance, to weight sequences in alignment to correct for over or under-representation
• Dual of a Voronoi diagram is a Delaunay triangulation
  • Connect all centers with lines (which are perpen. bisectors to edges)
  • Border of D.T. is Convex Hull
  • D.T. produces "fatest" possible triangles which makes it convenient for things such as finite element analysis.

Talk on Surfaces and Volumes / (C) Mark Gerstein (mbg@hyper.stanford.edu) / May 1996