Beta-skeletons - parametrized proximity graphs

University of Warsaw Repository

pl | en
 
 

Show simple item record

dc.contributor.advisor Kowaluk, Mirosław
dc.contributor.author Majewska, Gabriela [APD]
dc.date.issued 2016-06-22
dc.description.abstract In this dissertation, we show various results of our research on β-skeletons. The β-skeletons are graphs introduced first by Kirkpatrick and Radke, that belong to the family of proximity graphs, geometric graphs in which two vertices are connected with an edge if and only if they satisfy particular geometric requirements. For β-skeletons such edge between points v_1 and v_2 exists if no point from a given set lies inside a set called β-neighborhood (β-lune, respectively) of v_1 and v_2. Based on the shape of this set, we get two families of β-skeletons: lune-based β-skeletons and circle-based β-skeletons. β-skeletons find their applications in various areas: in machine learning, visual perception, pattern recognition, in geographic analysis, cartography, biology, and many more. Our results can be divided into three groups.1. β-skeletons in L_p metrics. We present a parallel algorithm that for a set of n points needs O(log^2 n) time to construct β-skeleton for β є [1,2] in PRAM-CREW model with O(n) processors. We also describe two algorithms computing β-spectrum for β є [1,2]. β-spectrum is a labeling of edges, where with each edge e we associate the maximum value of β such that e belongs to the β-skeleton for this β. One of these algorithms is sequential, and for a set of n points requires O(n log^2n) time. The second algorithm requires O(log^4 n) time in parallel CREW-PRAM model with O(n) processors. We also describe how to transform algorithms in CREW-PRAM model so that they can be used in distributed models. Hence, we show that it is possible to get poly-logarithmic distributed algorithms for computing β-skeleton and β-spectrum for β є [1,2] in model with O(n) processors.2. β-skeletons for points moving along line segments. While researching β-skeletons in L_p metrics, we encountered a problem of computing the β-skeleton for a set of points, where each point can move along some fixed line segment. This motivated us to research β-skeletons for sets of line segments. We provide an algorithm that for β≥1 computes the circle-based β-skeleton for a set S of n segments in the Euclidean plane in O(n^2 α (n) log n) time, and for the same values of β it computes lune-based β-skeleton in O(n^2 λ_4(n)), where α is a functional inverse of the Ackermann’s function, and λ_4(n) denotes the maximum possible length of a (n,4) Davenport-Schinzel sequence. For 0 < β < 1, we prove that the β-skeleton can be constructed in a O(n^3 λ_4(n)) time. In the special case of β = 1, which is a generalization of Gabriel Graph, we present an algorithm that computes the β-skeleton in O(n log n) time. 3. β-skeletons for sets of weighted points.We introduce a new family of graphs. Specifically, we present a definition of weighted β-skeletons for a set of points with weights such that in a space with appropriate distance function the weighted β-skeletons for β ≥1 are subgraphs of the graph dual to the additively weighted Voronoi diagram. For a set of n weighted points we show that the weighted β-skeleton can be computed in O(n^{5/2}log^{1/2}n) time for β <1, and in O(n^{3/2}log^{1/2}n) time for β≥1. Next, we characterize β-skeletons for a set of weighted points in a space with power distance function. In this case the circle-based β-skeletons for β ≥ 1 are connected to the dual graph of the power diagram. Based on these results, we present a general, distance-based definition of β-skeletons that can be used in various metrics spaces, and not only for sets of points, but also for other types of objects. We also explore the connection between β-skeletons and γ-neighborhood graphs, and between β-skeletons and α-shapes.
dc.description.abstract W tej rozprawie przedstawimy różne wyniki z naszych badań powiązanych z β-szkieletami. Definicja β-szkieletów została wprowadzona przez Kirpatricka i Radke. Należą one do rodziny grafów sąsiedztwa, grafów geometrycznych, gdzie dane dwa wierzchołki łączy krawędź wtedy i tylko wtedy, gdy spełniają one jakiś ustalony geometryczny warunek. Dla β-szkieletów taka krawędź istnieje między punktami v_1 i v_2, jeśli żaden punkt z ustalonego zbioru nie leży w obszarze nazywanym β-sąsiedztwem (odpowiednio, β-soczewką) v_1 i v_2. Ze względu na kształt tego obszaru rozróżniamy dwie rodziny β-szkieletów: β-szkielety soczewkowe i β-szkielety kołowe. β-szkielety znajdują zastosowania w różnych dziedzinach: w uczeniu maszynowym, percepcji wizualnej, w rozpoznawaniu wzorców, w analizie geograficznej, kartografii, biologii, i wielu innychNasze wyniki mogą być podzielone na trzy grupy. 1. β-szkielety w metrykach L_p. Przedstawiamy równoległy algorytm, który dla zbioru n punktów konstruuje β-szkielet dla βє [1,2] w czasie O(log^2 n) w modelu CREW-PRAM z O(n) procesorami. Opisujemy również dwa algorytmy obliczające β-spektrum dla β є [1,2], gdzie β-spektrum to przypisanie do każdej krawędzi takiej wartości parametru β, dla której krawędź ta należy do β-szkieletu. Jeden z nich jest sekwencyjny i dla zbioru n punktów działa w czasie O(nlog^2n). Drugi jest równoległy i wymaga czasu O(log^4n) w modelu CREW-PRAM z O(n) procesorami. Przedstawiamy również polilogarytmiczny algorytm rozproszony obliczający β-spektrum i β-szkielet dla β є [1,2] w modelu z O(n) procesorami.2. β-szkielety dla zbiorów punktów, które poruszają się wzdłuż odcinków.Badając β-szkielety w metrykach L_p natrafiliśmy na następujący problem. Chcemy policzyć β-szkielet dla zbioru punktów, z których każdy porusza się wzdłuż jakiegoś odcinka.By rozwiązać ten problem rozważamy β-szkielety dla zbiorów odcinków. Przedstawiamy algorytm, który dla β≥ 1 i dla zbioru n odcinków na płaszczyźnie euklidesowej oblicza β-szkielet kołowy w czasie O(n^2 α (n) log n), a β-szkielet soczewkowy w czasie O(n^2 λ_4(n)), gdzie α jest odwrotnością funkcji Ackermanna, a λ_4(n) oznacza maksymalną możliwą długość ciągu (n,4) Davenport'a-Schinzel'a. W przypadku β=1 przedstawiamy specjalny algorytm, który oblicza Graf Gabriela dla zbioru n odcinków w czasie O(nlog n). 3. β-szkielety dla zbiorów punktów z wagami.Prezentujemy również definicję ważonych β-szkieletów dla zbioru punktów z wagami. W przestrzeni z odpowiednią funkcją odległości te szkielety są dla β≥ 1 podgrafami grafu dualnego do addytywnie ważonego diagramu Voronoi. Przedstawiamy algorytm, który dla zbioru n punktów z wagami oblicza ważony β-szkielet w czasie O(n^{5/2}log^{1/2}n) dla β є [0,1] i w czasie O(n^{1/2}log^{1}/2}n) dla β≥1. Następnie definiujemy β-szkielety dla zbioru ważonych punktów w przestrzeni z odległością potęgową. W tym przypadku kołowe β-szkielety dla β≥ 1 są powiązane z grafem dualnym do diagramu potęgowego. Korzystając z tych wyników wprowadzamy uogólnioną definicję β-szkieletów opartą na odległościach pomiędzy punktami, którą można użyć w różnych przestrzeniach metrycznych, a także dla zbiorów obiektów innych niż punkty. Pokazujemy również związek pomiędzy β-szkieletami, a grafami γ-sąsiedztwa, oraz ten łączący β-szkielety i α-kształty.
dc.language.iso en
dc.rights 10daysAccess
dc.subject β-skeletons
dc.subject β-spectrum
dc.subject Gabriel Graph
dc.subject Relative Neighborhood Graph
dc.subject Delaunay Triangulation
dc.subject Voronoi Diagram
dc.subject power diagram
dc.subject β-szkielety
dc.subject β-spektrum
dc.subject Graf Gabriela
dc.subject graf relatywnego sąsiedztwa
dc.subject triangulacja Delaunay
dc.subject diagram Voronoi
dc.subject diagram potęgowy
dc.title Beta-skeletons - parametrized proximity graphs
dc.title.alternative Beta-szkielety - parametryzowalne grafy sąsiedztwa
dc.title.alternative Beta-skeletons - parametrized proximity graphs
dc.type info:eu-repo/semantics/doctoralThesis
dc.contributor.department Wydział Matematyki, Informatyki i Mechaniki
dc.date.defence 2016-12-20
dc.identifier.apd 18383
dc.description.osid 114499
dc.contributor.email G.Majewska@mimuw.edu.pl

Files in this item

Files Size Format View

This item appears in the following Collection(s)

Show simple item record

Search Repository


Advanced Search

Browse

My Account

Statistics