Seminar of Theoretical Computer Science - Andrej Ferko (16.11.2018)

Friday 16.11.2018 at 11:00, Lecture room M/213

14. 11. 2018 10.08 hod.
By: Rastislav Královič

Andrej Ferko:
Neighbourhood Graphs and Locally Minimal Triangulations

Abstract:
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