Geometric Proximity Graphs

Abstract

This chapter focuses on geometric proximity graphs which can serve as a powerful tool to capture the structure or shape of otherwise unstructured point sets. These graphs have numerous applications in areas such as computer graphics, computer vision, geography, information retrieval, routing in ad-hoc networks, and computational biology, among many others. The chapter presents a small number of neighborhood graphs (other than polygonal meshes) and a few applications in computer graphics, where they can help to detect structure in point clouds. There are other geometric graphs that are more or less closely related to proximity graphs, such as the minimum spanning tree (MST) and the Delaunay graph (DG). The MST spans (i.e., connects) all points by a tree of minimal length. The DG is the dual of the Voronoi diagram.