APPLICATIONS AND RELATIVES

The following sections are included:

• Distance problems

  • Post office problem

  • Nearest neighbors and the closest pair

  • Largest empty and smallest enclosing circle

• Subgraphs of Delaunay triangulations

  • Minimum spanning trees and cycles

  • α-shapes and shape recovery

  • β-skeletons and relatives

  • Paths and spanners

• Supergraphs of Delaunay triangulations

  • Higher-order Delaunay graphs

  • Witness Delaunay graphs

• Geometric clustering

  • Partitional clustering

  • Hierarchical clustering

• Motion planning

  • Retraction

  • Translating polygonal robots

  • Clearance and path length

  • Roadmaps and corridors