ABSTRACT
In 1969, Gabriel and Sokal [GS69] presented a method for associating a graph to a set of geographic data points P by connecting points x, y ∈ P with an edge if and only if the closed disk having the segment xy as diameter contained no other point of P . This geometric graph, called the Gabriel graph of P , is just one example of what have come to be called proximity graphs. Loosely speaking, a proximity graph is a geometric graph (i.e., a straight-line drawing) constructed from a set P of points in some metric space by connecting pairs of points that are deemed to be “sufficiently” close together. A set P can give rise to a variety of different proximity graphs depending upon the definition of closeness used.
