Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Beta skeleton
Résumé
In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.
Let β be a positive real number, and calculate an angle θ using the formulas
For any two points p and q in the plane, let Rpq be the set of points for which angle prq is greater than θ. Then Rpq takes the form of a union of two open disks with diameter βd(p,q) for β ≥ 1 and θ ≤ π/2, and it takes the form of the intersection of two open disks with diameter d(p,q)/β for β ≤ 1 and θ ≥ π/2. When β = 1 the two formulas give the same value θ = π/2, and Rpq takes the form of a single open disk with pq as its diameter.
The β-skeleton of a discrete set S of points in the plane is the undirected graph that connects two points p and q with an edge pq whenever Rpq contains no points of S. That is, the β-skeleton is the empty region graph defined by the regions Rpq. When S contains a point r for which angle prq is greater than θ, then pq is not an edge of the β-skeleton; the β-skeleton consists of those pairs pq for which no such point r exists.
Some authors use an alternative definition in which the empty regions Rpq for β > 1 are not unions of two disks but rather lenses (more often called in this context "lunes"), intersections of two congruent disks with diameter βd(pq), such that line segment pq lies on a radius of both disks and such that the points p and q both lie on the boundary of the intersection. As with the circle-based β-skeleton, the lune-based β-skeleton has an edge pq whenever region Rpq is empty of other input points. For this alternative definition, the relative neighborhood graph is a special case of a β-skeleton with β = 2. The two definitions coincide for β ≤ 1, and for larger values of β the circle-based skeleton is a subgraph of the lune-based skeleton.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.