Gabriel graph

Gabriel graph

A Gabriel graph is a certain graph that connects a set of points in the Euclidean plane. Two points "P" and "Q" are connected by an edge in the Gabriel graph whenever the disk having line segment "PQ" as its diameter contains no other points from the given point set. More generally, in any dimension, the Gabriel graph connects any two points forming the endpoints of the diameter of an empty sphere. Gabriel graphs are named after K. R. Gabriel, who introduced them in a paper with R. R. Sokal in 1969.

The Gabriel graph is a subgraph of the Delaunay triangulation; it can be found in linear time if the Delaunay triangulation is given (Matula and Sokal, 1980). The Gabriel graph contains as a subgraph the Euclidean minimum spanning tree and the nearest neighbor graph. It is an instance of a beta-skeleton.

References

*citation
last1 = Gabriel | first1 = K. R. | last2 = Sokal | first2 = R. R.
title = A new statistical approach to geographic variation analysis
journal = Systematic Zoology
year = 1969
pages = 259–270
volume = 18
doi = 10.2307/2412323
.

*citation
last1 = Matula | first1 = D. W. | last2 = Sokal | first2 = R. R.
title = Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane
journal = Geogr. Anal.
year = 1980
pages = 205–222
volume = 12
.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Gabriel — bezeichnet: den Erzengel Gabriel (Erzengel) einen männlichen Vornamen und Familiennamen, siehe Gabriel (Name) eine Käsesorte aus Irland, siehe Gabriel (Käse) einen internetbasierten Informationsdienst für die europäischen Nationalbibliotheken,… …   Deutsch Wikipedia

  • GABRIEL — bezeichnet: den Erzengel Gabriel (Erzengel) einen männlichen Vornamen und Familiennamen, Gabriel (Name) eine Käsesorte aus Irland, siehe Gabriel (Käse) einen internetbasierten Informationsdienst für die europäischen Nationalbibliotheken, siehe… …   Deutsch Wikipedia

  • Gabriel (disambiguation) — Gabriel is a messenger angel or an archangel. Gabriel may also refer to: * Gabriel (name), a given name or surname * Gabriel, a character in The Giver * Gabriel , title of a song by French Moroccan singer Najoua Belyzel * Gabriel missile, an… …   Wikipedia

  • Gabriel's Horn — (also called Torricelli s trumpet) is a figure invented by Evangelista Torricelli which has infinite surface area, but finite volume. The name refers to the tradition identifying the archangel Gabriel with the angel who blows the horn to announce …   Wikipedia

  • Gabriel Andrew Dirac — (* 13. März 1925 in Budapest; † 20. Juli 1984 in Arlesheim) war ein ungarisch britischer Mathematiker, der sich mit Graphentheorie beschäftigte. Gabriel Dirac war der Sohn von Eugene Paul Wigners Schwester Margit aus erster Ehe. Als diese 1937… …   Deutsch Wikipedia

  • Gabriel Andrew Dirac — (1925–1984) was a mathematician who mainly worked in graph theory. He stated a sufficient condition for a graph to contain a Hamiltonian circuit.Dirac received his Ph.D. in 1952 from the University of London. [MathGenealogy|id=42235] Dirac was… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Nearest neighbor graph — A nearest neighbor graph of 100 points in the Euclidean plane. The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points in the plane with Euclidean distance) is a directed graph with P being its… …   Wikipedia

  • Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”