| dbo:abstract
|
- In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation. The Urquhart graph was described by , who suggested that removing the longest edge from each Delaunay triangle would be a fast way of constructing the relative neighborhood graph (the graph connecting pairs of points and when there does not exist any third point that is closer to both and than they are to each other). Since Delaunay triangulations can be constructed in time , the same time bound holds for the Urquhart graph as well. Although it was later shown that the Urquhart graph is not exactly the same as the relative neighborhood graph, it can be used as a good approximation to it. The problem of constructing relative neighborhood graphs in time, left open by the mismatch between the Urquhart graph and the relative neighborhood graph, was solved by . Like the relative neighborhood graph, the Urquhart graph of a set of points in general position contains the Euclidean minimum spanning tree of its points, from which it follows that it is a connected graph. (en)
- De Urquhartgraaf (UG) van een verzameling S van punten in het vlak is een deelgraaf van de Delaunay-triangulatie (DT) van S. De Urquhartgraaf bekomt men door van elke driehoek in de Delaunay-triangulatie de langste zijde te verwijderen. Roderick B. Urquhart stelde in een publicatie uit 1980 voor dat deze constructie een snel algoritme zou leveren om de relative neighborhood graph (RNG) van een verzameling punten te bepalen. In de RNG zijn twee punten p en q met elkaar verbonden als er geen enkel ander punt is dat dichter bij p en q ligt dan p en q zelf. Maar Godfried Toussaint, de bedenker van de RNG, toonde met een tegenvoorbeeld aan dat in het algemeen de RNG slechts een deelgraaf van de Urquhartgraaf is. De Urquhartgraaf is dus niet altijd gelijk aan de RNG maar is er wel een goede benadering van. De Gabrielgraaf (GG) is een graaf waarin twee punten p en q verbonden zijn als de cirkel met diameter pq geen andere punten van de verzameling S omvat. Deze graaf ligt tussen de UG en de Delaunay-triangulatie in. In het algemeen geldt: RNG(S) ⊆ UG(S) ⊆ GG(S) ⊆ DT(S) (nl)
- Граф Уркхарта множества точек на плоскости, названный в честь Родерика Б. Уркхарта, получается путём удаления самого длинного ребра из каждого треугольника в триангуляции Делоне. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2837 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Граф Уркхарта множества точек на плоскости, названный в честь Родерика Б. Уркхарта, получается путём удаления самого длинного ребра из каждого треугольника в триангуляции Делоне. (ru)
- In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation. Like the relative neighborhood graph, the Urquhart graph of a set of points in general position contains the Euclidean minimum spanning tree of its points, from which it follows that it is a connected graph. (en)
- De Urquhartgraaf (UG) van een verzameling S van punten in het vlak is een deelgraaf van de Delaunay-triangulatie (DT) van S. De Urquhartgraaf bekomt men door van elke driehoek in de Delaunay-triangulatie de langste zijde te verwijderen. De Gabrielgraaf (GG) is een graaf waarin twee punten p en q verbonden zijn als de cirkel met diameter pq geen andere punten van de verzameling S omvat. Deze graaf ligt tussen de UG en de Delaunay-triangulatie in. In het algemeen geldt: RNG(S) ⊆ UG(S) ⊆ GG(S) ⊆ DT(S) (nl)
|
| rdfs:label
|
- Urquhartgraaf (nl)
- Граф Уркхарта (ru)
- Urquhart graph (en)
- Граф Уркгарта (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
