dc.contributor.author
Seiferth, Paul
dc.date.accessioned
2018-06-07T17:46:16Z
dc.date.available
2016-08-24T12:29:37.953Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/4233
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-8433
dc.description.abstract
Let P be a set of n point sites in the plane. The unit disk graph UD(P) on P
has vertex set P and an edge between two sites p,q of P if and only if p and q
have Euclidean distance |pq| <= 1. If we interpret P as centers of disks with
diameter 1, then UD(P) is the intersection graph of these disks, i.e., two
sites p and q form an edge if and only if their corresponding unit disks
intersect. Two natural generalizations of unit disk graphs appear when we
assign to each point p of P an associated radius r_p > 0. The first one is the
disk graph D(P), where we put an edge between p and q if and only if |pq| <=
r_p + r_q, meaning that the disks with centers p and q and radii r_p and r_q
intersect. The second one yields a directed graph on P, called the
transmission graph of P. We obtain it by putting a directed edge from p to q
if and only if |pq| <= r_p, meaning that q lies in the disk with center p and
radius r_p. For disk and transmission graphs we define the radius ratio Psi to
be the ratio of the largest and the smallest radius that is assigned to a site
in P. It turns out that the radius ratio is an important measure of the
complexity of the graphs and some of our results will depend on it. For these
three classes of disk intersection graphs we present data structures and
algorithms that solve four types of graph theoretic problems: dynamic
connectivity, routing, spanner construction, and reachability oracles; see
below for details. For disk and unit disk graphs, we improve upon the
currently best known results, while the problems we consider for transmission
graphs abstain non-trivial solutions so far. Dynamic Connectivity: First, we
present a data structure that maintains the connected components of a unit
disk graph UD(P) when P changes dynamically. It takes O(log^2 n) amortized
time to insert or delete a site in P and O(log(n)/loglog(n)) worst-case time
to determine if two sites are in the same connected component. Here, n is the
maximum size of P at any time. A simple variant improves the amortized update
time to O(log(n)loglog(n)) at the cost of a slightly increased worst-case
query time of O(log(n)). Using more advanced data structures, we can extend
our approach to disk graphs. While the worst-case query time remains
O(log(n)/loglog(n)), an update now requires O(Psi^2 2^(alpha(n))log^(10)(n))
amortized expected time, where Psi is the radius ratio of the disk graph and
alpha(n) is the inverse Ackermann function. Routing: As the second problem, we
consider routing in unit disk graphs. A routing scheme R for UD(P) assigns to
each site s of P a label l(s) and a routing table rho(s). For any two sites s
and t of P, the scheme R must be able to route a packet from s to t in the
following way: given a current site r (initially, r = s), a header h
(initially empty), and the target label l(t), the scheme R may consult the
current routing table rho(r) to compute a new site r' and a new header h',
where r' is a neighbor of r in UD(P). The packet is then routed to r', and the
process is repeated until the packet reaches t. The resulting sequence of
sites is called the routing path. The stretch of R is the maximum ratio of the
(Euclidean) length of the routing path produced by R and the shortest path in
UD(P), over all pairs of distinct sites in P. For any given eps > 0, we show
how to construct a routing scheme for UD(P) with stretch 1+eps using labels of
O(log(n)) bits and routing tables of O(eps^(-5)log^2(n)log^2(D)) bits, where D
is the (Euclidean) diameter of UD(P). The header size is O(log(n)log(D)) bits.
Spanners: Next, we construct sparse approximations of transmission and disk
graphs. Let G be a transmission graph. A t-spanner for G is a subgraph H of G
with vertex set P so that for any two sites p and q of P, we have d_H(p, q) <=
td_G(p, q), where d_H and d_G denote the shortest path distance in H and G
(with Euclidean edge lengths). We show how to compute a t-spanner for G with
O(n) edges in O(n(log(n) + log(Psi))) time, where Psi is the radius ratio of
P. Utilizing advanced data structures, we obtain a construction that runs in
O(n log^5(n)) time, independent of Psi. This construction can be adapted to
disk graphs and gives a t-spanner for D(P) in expected time
O(n2^(alpha(n))log^(10)(n)), where alpha(n) is the inverse Ackermann function.
As an application we show that our t-spanner can be used to find a BFS tree in
a transmission or disk graph for any given start vertex in O(n log(n))
additional time. Reachability Oracles: Finally, we compute reachability
oracles for transmission graphs. These are data structures that answer
reachability queries: given two sites p and q, is there a directed path
between them? The quality of an oracle is measured by the space S(n), the
query time Q(n), and the preproccesing time. We present three reachability
oracles whose quality depends on the radius ratio Psi: the first one works
only for Psi < sqrt(3) and achieves Q(n) = O(1) with S(n) = O(n) and
preprocessing time O(n log(n)); the second data structure gives Q(n) = O(Psi^3
sqrt(n)) and S(n) = O(Psi^3 n^(3/2)); the third data structure is randomized
with Q(n) = O(n^(2/3)(log(n) + log(Psi))) and S(n) = O(n^(5/3)(log(n) +
log(Psi))) and answers queries correctly with high probability. As a second
application for our spanners, we employ them to achieve a fast preprocessing
time for our reachability oracles.
de
dc.description.abstract
Sei P eine Menge von n Punkten in der Ebene. Der Unit Disk Graph von P, UD(P),
hat P als Knotenmenge. Zwei Knoten p,q bilden eine Kante in UD(P) genau dann,
wenn p und q euklidischen Abstand |pq| <= 1 haben. Eine Verallgemeinerung von
Unit Disk Graphen sind Transmissionsgraphen. Jeder Punkt p aus P hat einen
Radius r_p, und wir betrachten einen gerichteten Graphen G mit Knotenmenge P.
Es existiert eine gerichtete Kante pq in G genau dann, wenn |pq| <= r_p, also
wenn q im Kreis um p mit Radius r_p liegt. Wir studieren die folgenden
Probleme für Unit Disk und Transmissionsgraphen. Dynamischer Zusammenhang: Wir
beschreiben eine Datenstruktur zum Verwalten der Zusammenhangskomponenten
eines Unit Disk Graphen UD(P) wenn Punkte in P eingefügt oder gelöscht werden
können. Die Datenstruktur kann zu jedem Zeitpunkt Zusammenhangsanfragen
beantworten: Gegeben zwei Anfragepunkte p,q aus P, existiert ein Pfad von p zu
q in UD(P)? Alle Operationen benötigen O(polylog(n)) Zeit. Routing: Wir
zeigen, dass es möglich ist, Datenpakete durch einen Unit Disk Graphen zu
routen, indem in jedem Schritt der aktuelle Knoten lokal bestimmt, zu welchem
seiner Nachbarn er das Paket weiter sendet. Das Routingschema besitzt dazu
eine Menge von lokalen Informationen an jedem Knoten (Routingtabellen), ein
Bezeichner an jedem Knoten, und einen veränderlichen Vorspann im Datenpaket.
Die benötigte Größe ist jeweils O(polylog(n)). Wir zeigen, dass ein Datenpaket
zwischen beliebigen Knoten p und q in UD(P) geroutet werden kann und es dabei
einem approximativ kürzesten Pfad von p nach q folgt. Spanngraphen:
Transmissionsgraphen können eine quadratische Anzahl an Kanten besitzen. Wir
zeigen, dass wir zu jedem Transmissionsgraphen G einen aufspannenden
Teilgraphen H von G finden können, der nur eine lineare Anzahl von Kanten
besitzt und gleichzeitig die kürzesten Pfade zwischen allen Paaren von Knoten
in G approximiert. Der Teilgraph H wird als Spanngraph bezeichnet. Unser
Algorithmus berechnet einen Spanngraph in Zeit O(n polylog(n)), wenn G als
Punktmenge mit Radien gegeben ist. Erreichbarkeitsorakel: Wir beschreiben drei
Datenstrukturen, die Erreichbarkeitsanfragen in einem Transmissionsgraphen G
beantworten können: gegeben zwei Anfragepunkte p,q aus P, existiert ein
gerichteter Pfad von p zu q in G? Wir bezeichnen solche Datenstrukturen als
Erreichbarkeitsorakel. Unsere Orakel hängen von dem Verhältnis Psi des größten
und des kleinsten Radius von Punkten in P ab. Wenn Psi < sqrt(3) ist, dann
können wir ein Orakel mit O(1) Anfragezeit und O(n) Platz konstruieren. Für
größere Werte von Psi präsentieren wir ein Orakel mit Anfragezeit O(Psi^3
sqrt(n)) und Platzbedarf O(Psi^3 n^(3/2)). Unser letztes Orakel hat nur noch
logarithmische Abhängigkeit von Psi. Die Anfragezeit ist
O(n^(2/3)log^(1/3)(Psi) log^(2/3)(n)) und der Platzbedarf O(n^(5/3)(log(Psi) +
log(n))log^(1/3)(Psi)log^(2/3)(n)).
de
dc.format.extent
xii, 113 Seiten
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
unit disk graph
dc.subject
reachability oracles
dc.subject
data structures
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::000 Informatik, Informationswissenschaft, allgemeine Werke
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::516 Geometrie
dc.title
Disk Intersection Graphs: Models, Data Structures, and Algorithms
dc.contributor.contact
pseiferth87@gmail.com
dc.contributor.firstReferee
Prof. Dr. Wolfgang Mulzer
dc.contributor.furtherReferee
Prof. Dr. Christian Knauer
dc.date.accepted
2016-08-19
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000102864-4
dc.title.translated
Schnittgraphen von Kreisscheiben: Modelle, Datenstrukturen und Algorithmen
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000102864
refubium.mycore.derivateId
FUDISS_derivate_000000019890
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access