Routing and Stabbing

Abstract

ROUTING. Let G be a simple, connected, undirected graph. We consider routing with preprocessing in G. In a preprocessing step, each vertex of G receives a label and a routing table. Then, we must be able to route a packet between any two vertices s and t of G, where each step may use only the label of the target node t, the routing table of the current node and the packet header. This problem has been studied extensively for general graphs, where efficient routing schemes with polylogarithmic routing tables have turned out to be impossible. Thus, special graph classes are of interest.

Let P be an x-monotone orthogonal polygon with n vertices. We call P a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points p and q in P are co-visible if and only if the (axis-parallel) rectangle spanned by p and q completely lies in P. In the r-visibility graph Vis(P) of P, we connect two vertices of P with a unit weighted edge if and only if they are co-visible. We present a routing scheme for visibility graphs of simple and of double histograms that have label size log n and table size O(log n deg(v)) for each vertex v of P, where deg(v) is the degree of v in Vis(P). In simple histograms we can route along a shortest path and need no additional header, whereas in double histograms we need headers of size log n and we can route on a path that has twice the length of an optimal path. The preprocessing time is in both cases O(m), where m is the number of edges in Vis(P).

Let V be a set of n sites in the plane. The unit disk graph DG(V) of V is the graph with vertex set V where two sites v and w are adjacent if and only if their Euclidean distance is at most 1. The edge weights correspond to the Euclidean distance of its endpoints. Moreover, we use D to denote the diameter of DG(V). We show that for any given eps>0, we can construct a routing scheme for DG(V) that achieves stretch 1+eps, has label size O(eps^(-1)log D log^3n/loglog n), table size eps^(-O(eps^(-2)))log^3n(1+log D/loglog n) and the header needs at most O(log^2n/loglog n) bits. The preprocessing time is O(eps^(-1)n^2 log^2 n).

STABBING. Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. This provides a simple---albeit slightly weaker---algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points.

ROUTEN. Wir betrachten Routen mit Vorverarbeitung in einem Graphen G. Während der Vorverarbeitung von G erhält jeder Knoten ein Label und eine Routingtabelle. Danach müssen wir in der Lage sein ein Datenpaket zwischen je zwei Knoten s und t von G zu routen, wobei jeder Schritt lediglich das Label von t, die Routingtabelle von s und den Header des Pakets benutzen darf. Das Routingproblem wurde bereits ausführlich für allgemeine Graphen erforscht. Es hat sich herausgestellt, dass kompakte (polylogarithmisch große Routingtabellen) und effiziente Routingschemata für allgemeine Graphen nicht existieren.

Sei P ein x-monotones orthogonales Polygon mit n Ecken. Wir bezeichnen P als einfaches Histogramm, wenn der obere Teil des Randes eine einzelne Strecke ist. P ist ein doppeltes Histogramm, wenn es eine horizontale Sehne gibt, welche vom linken zum rechten Rand geht. Zwei Punkte p und q sind co-sichtbar genau dann, wenn das achsenparallele Rechteck, aufgespannt von p und q, komplett in P liegt. Im r-Sichtbarkeitsgraphen Vis(P) gibt es eine Kante zwischen je zwei co-sichtbaren Ecken von P. Wir präsentieren ein Routingschema für Sichtbarkeitsgraphen von einfachen und doppelten Histogrammen, welches Labelgröße log n und Routingtabellengröße O(log n deg(v)) für jede Ecke v von P erreicht, wobei deg(v) der Grad von v in Vis(P) ist. In einfachen Histogrammen können wir entlang eines kürzesten Weges routen und benötigen keinen zusätzlichen Header. Für doppelte Histogramme benötigen wir einen Header der Größe log n und erreichen Stretch 2. In beiden Fällen ist die Vorverarbeitungszeit asymptotisch zur Anzahl der Kanten von Vis(P).

Sei V eine Menge von n Punkten in der Ebene. Der Einheitskreisgraph DG(V) ist ein Graph mit Knotenmenge V und einer Kante zwischen je zwei Knoten v und w, wenn ihr Euklidischer Abstand höchstens 1 ist. Die Kantengewichte sind die Euklidischen Abstände. Sei außerdem D der Durchmesser des Graphen. Wir konstruieren für jedes eps>0 ein Routingschema für DG(V). Das Schema erreicht Stretch 1+eps, Labelgröße O(eps^(-1)log Dlog^3n/loglog n), Routingtabellengröße eps^(-O(eps^(-2)))log^3n(1+log D/loglog n) und Headergröße O(log^2n/loglog n). Die Vorverarbeitungszeit beträgt O(eps^(-1)n^2log^2 n).

PIERCEN. Sei D eine Menge von n sich paarweise schneidenden Kreisscheiben in der Ebene. Eine Punktmenge P pierct D genau dann, wenn jede Kreisscheibe aus D mindestens einen Punkt aus P enthält. Wir präsentieren einen deterministischen Algorithmus, der O(n) Zeit benötigt um 5 Punkte zu finden, die D piercen. Damit liefern wir eine einache, wenn auch etwas schwächere, algorithmische Version des klassischen Ergebnisses von Danzer, wonach eine solche Menge D immer von 4 Punkten gepierct werden kann. Außerdem geben wir ein einfaches Beispiel mit 13 sich paarweise schneidenden Kreisscheiben an, welches nicht von 3 Punkten gepierct werden kann.