A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Geometric spanner (en)
- Геометрический остов (ru)
- Геометричний кістяк (uk)
|
| rdfs:comment
| - A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. (en)
- Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется остова. В вычислительной геометрии концепцию первым обсуждал Л.П. Чу в 1986, хотя термин «spanner» (остов) в статье упомянут не был. (ru)
- Геометричний кістяк (англ. geometric spanner) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають кістяка. В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986), хоча термін «spanner» (кістяк) у статті не згадано. (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. The notion of graph spanners has been known in graph theory: t-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric. Spanners may be used in computational geometry for solving some proximity problems. They have also found applications in other areas, such as in motion planning, in telecommunication networks: network reliability, optimization of roaming in mobile networks, etc. (en)
- Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется остова. В вычислительной геометрии концепцию первым обсуждал Л.П. Чу в 1986, хотя термин «spanner» (остов) в статье упомянут не был. Понятие остовных деревьев известно в теории графов — t-остова, это остовные подграфы графов с похожими свойствами растяжения, где расстояние между вершинами графа определяется в терминах теории графов. Поэтому геометрические остовы являются остовными деревьями полных графов, вложенных в плоскость, в которых веса рёбер равны расстояниям между вершинами в соответствующей метрике. Остовы могут быть использованы в вычислительной геометрии для решения некоторых . Они находят также приложения в других областях, таких как , в коммуникационных сетях — надёжность сети, оптимизация роуминга в мобильных сетях и т.д.. (ru)
- Геометричний кістяк (англ. geometric spanner) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають кістяка. В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986), хоча термін «spanner» (кістяк) у статті не згадано. Поняття кістякового дерева відоме в теорії графів: t-кістяки — це кістякові підграфи графів зі схожими властивостями розтягування, де відстань між вершинами графа визначається в термінах теорії графів. Тому геометричні кістяки є кістяковими деревами повних графів, укладених у площину, в яких ваги ребер дорівнюють відстаням між вершинами у відповідній метриці. Остовы можна використати в обчислювальній геометрії для розв'язання деяких . Вони мають також застосування в інших галузях, таких як планування руху, в комунікаційних мережах — надійність мережі, оптимізація роумінгу в мобільних мережах тощо. (uk)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)