Seminár z teoretickej informatiky - Andrej Ferko (16.11.2018)

v piatok 16.11.2018 o 11:00 hod. v miestnosti M/213

14. 11. 2018 10.01 hod.
Od: Rastislav Královič

Prednášajúci: Andrej Ferko

Názov: Neighbourhood Graphs and Locally Minimal Triangulations

Termín: 16.11.2018, 11:00 hod., M/213

Abstrakt:
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. We focus on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and show 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.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php