Grafy sousednosti a lokálně minimální triangulace
| Autor: | Martin Maňák, Ivana Kolingerová, Tomáš Vomáčka, Andrej Ferko |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Locally minimal triangulation
lokálně minimální triangulace kinetický problém Delaunay triangulation Computer science K-nearest neighbour graph Computation Closeness Neighbourhood (graph theory) graf nejbližších sousedů Nearest neighbour Neighbourhood graph Graph graf k nejbližších sousedů Combinatorics Kinetic problem Delaunayova triangulace ComputingMethodologies_GENERAL Nearest neighbour graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783662580387 |
| Popis: | Grafy sousednosti (proximity), jako je graf nejbližších sousedů, nejbližší dvojice, graf relativního sousedství a graf k nejbližších sousedů jsou nástroje užitečné v mnoha problémech, kde se zkoumají vzájemné vztahy, podobnost a blízkost objektů. Článek se věnuje vztahu grafů sousednosti k lokálně minimální triangulaci (LMT) a ukazuje, že ve většině případů LMT obsahuýje všechny hrany Neighbourhood (or proximity) graphs, such as nearest neighbour graph, closest pairs, relative neighbourhood graph and k-nearest neighbour graph are useful tools in many tasks inspecting mutual relations, similarity and closeness of objects. Some of neighbourhood graphs are subsets of Delaunay triangulation (DT) and this relation can be used for efficient computation of these graphs. This paper concentrates on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and shows that, although generally these graphs are not LMT subgraphs, in most cases LMT contains all or many edges of these graphs. This fact can also be used for the neighbourhood graphs computation, namely in kinetic problems, because LMT computation is easier. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|