About: Yao graph     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FYao_graph&invfp=IFP_OFF&sas=SAME_AS_OFF

In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance. Andrew Yao used these graphs to construct high-dimensional Euclidean minimum spanning trees.

AttributesValues
rdfs:label
  • Граф Яо (ru)
  • Yao graph (en)
  • Граф Яо (uk)
rdfs:comment
  • Граф Яо — вид геометричного кістяка, зважений неорієнтований граф, що з'єднує множину геометричних точок, зі властивістю, що для будь-якої пари точок у графі найкоротший шлях між ними має довжину, що не перевищує на сталий множник їхньої евклідової відстані. Названо на честь Ендрю Яо. (uk)
  • Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния. Назван в честь Эндрю Яо. (ru)
  • In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance. Andrew Yao used these graphs to construct high-dimensional Euclidean minimum spanning trees. (en)
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/Yao_graph.svg
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
thumbnail
has abstract
  • In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance. The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced rays, partitioning the plane into sectors with equal angles, and to connect each point to its nearest neighbor in each of these sectors. Associated with a Yao graph is an integer parameter k ≥ 6 which is the number of rays and sectors described above; larger values of k produce closer approximations to the Euclidean distance. The stretch factor is at most , where is the angle of the sectors. The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially with the dimension. Andrew Yao used these graphs to construct high-dimensional Euclidean minimum spanning trees. (en)
  • Граф Яо — вид геометричного кістяка, зважений неорієнтований граф, що з'єднує множину геометричних точок, зі властивістю, що для будь-якої пари точок у графі найкоротший шлях між ними має довжину, що не перевищує на сталий множник їхньої евклідової відстані. Названо на честь Ендрю Яо. (uk)
  • Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния. Назван в честь Эндрю Яо. (ru)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 50 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software