Mánudaginn 1. júni kl. 10:00 mun Arnór Friðriksson verja 60 ECTS verkefni sitt til meistaragráðu í tölvunarfræði „Methods of constructing and analyzing points using graph theory"

• Stofa: M119 og eru öll velkomin.

Leiðbeinendur:  Szabolcs-Endre Horvát, lektor, Tölvunarfræðideild, Háskólinn í Reykjavík

Prófdómarar:

María Óskardóttir, dósent, Tölvunarfræðideild, Háskólinn í Reykjavík

Luca Aceto, prófessor, Tölvunarfræðideild, Háskólinn í Reykjavík

Útdráttur: 

β-skeletons are a type of parametrized proximity graph that represents neighbourhood relations of spatial point sets, and accurately captures their local structure in arbitrary dimensions.  β-skeletons have recently been proposed as a tool for characterizing spatial point patterns through the corresponding proximity graphs.  To aid such analysis, and help better understand the relationship between the characteristics of point patterns and their proximity graphs, artificial point sets with controlled structures are investigated.  We consider both the direct and inverse problem: investigating the graphs that result from known point sets, and constraining the resulting graph in some way and producing a point set that induces it.  We examine two types of point patterns: Fibonacci lattices (including a detailed treatment of their properties), and patterns generated so as to keep their β-skeletons connected even for high β. As part of this work, we developed an efficient software implementation for computing β-skeletons in arbitrary dimensions, and integrated them into the popular igraph network analysis library.