[SOLVED] CS algorithm Routing Among Obstacles1

Routing Among Obstacles1
Andre van Renssen
1Joint work with Prosenjit Bose, Rolf Fagerberg, Matias Korman, and Sander Verdonschot

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Introduction
We want:
a connected graph,
few edges (linear in number of nodes), short paths between nodes,
preferably no central nodes.
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Obstacles
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Obstacles
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Obstacles
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Obstacles
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Obstacles
We want:
a connected graph,
in the presence of obstacles,
few edges (linear in number of nodes), short paths between nodes,
preferably no central nodes.
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of visible vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of visible vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of visible vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Graph H is a t-spanner of a graph G if and only if
for all pairs of visible vertices u and v , H (u , v ) t G (u , v )
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Delaunay graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: Greedy spanner
Delaunay graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
Greedy spanner Delaunay graphs Yao graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
Greedy spanner Delaunay graphs Yao graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
Greedy spanner Delaunay graphs Yao graphs
-graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
w x
v y
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
w x
v y
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
w x
v y
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
w x
v y
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
w x
v y
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained m -Graph
u
All constrained m -graphs with m 6 cones are spanners
w x
v y
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Great! We have a spanner! Now what?
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
t
s
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
t
s
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Not feasible when the graph is very large
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Not feasible when the graph is very large Random walk
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Not feasible when the graph is very large
Random walk
Path can be very long
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Not feasible when the graph is very large Random walk
Path can be very long
Local competitive routing algorithm
Local: uses only information about source, target, and neighbors of
current vertex
Competitive: gives guarantees about length of the path
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing
Use SSSP algorithm
Not feasible when the graph is very large Random walk
Path can be very long
Local competitive routing algorithm
Local: uses only information about source, target, and neighbors of
current vertex
Competitive: gives guarantees about length of the path
No such algorithms known in the constrained setting
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained 6-Graph
v u
s
t
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained 6-Graph
v u
s
t
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained 6-Graph
v u
s
t
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained 6-Graph
t
v u
s
Andre van Renssen

Introduction Routing Conclusion & Open Problems
The Constrained 6-Graph
t
v u
s
Andre van Renssen

Introduction Routing Conclusion & Open Problems
General Routing Strategy
Alternate between:
Use -routing until we get stuck
Route to an endpoint of the constraint blocking you
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
u
w
v
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
u
w
v
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing to a Constraint
u
w
z
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
w
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Bounding the Number of Steps
Intuitively:
If we always route to the endpoint of the constraint that is closest to the destination, we shouldnt cycle
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Bounding the Number of Steps
Intuitively:
If we always route to the endpoint of the constraint that is closest to the destination, we shouldnt cycle
Recall: Constraints are edges of the visibility graph
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Bounding the Number of Steps
Intuitively:
If we always route to the endpoint of the constraint that is closest to the destination, we shouldnt cycle
Recall: Constraints are edges of the visibility graph
Formally:
Need to show that we make some sort of progress:
Always get closer?
Can only route to a constraint once?
Every vertex is visited a constant number of times? Potential function?
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Bounding the Number of Steps
Intuitively:
If we always route to the endpoint of the constraint that is closest to the destination, we shouldnt cycle
Recall: Constraints are edges of the visibility graph
Formally:
Need to show that we make some sort of progress:
Always get closer? No
Can only route to a constraint once? Unclear Every vertex is visited a constant number of times? No
Potential function? Unclear
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Termination
-routing phase always gets closer, so n steps per phase
Routing to a constraint visits a vertex at most once, so n steps per phase
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Termination
-routing phase always gets closer, so n steps per phase
Routing to a constraint visits a vertex at most once, so n steps per phase
Bounding the number of phase alternations:
t
u
z
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Termination
-routing phase always gets closer, so n steps per phase
Routing to a constraint visits a vertex at most once, so n steps per phase
Bounding the number of phase alternations:
t
u
z
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Termination
-routing phase always gets closer, so n steps per phase
Routing to a constraint visits a vertex at most once, so n steps per phase
Bounding the number of phase alternations:
t
z
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Termination
-routing phase always gets closer, so n steps per phase
Routing to a constraint visits a vertex at most once, so n steps per phase
Bounding the number of phase alternations: 2k alternations t
z
u
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
All -routing phases combined take O(n) steps
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
All -routing phases combined take O(n) steps Route at most once to each constraint
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
All -routing phases combined take O(n) steps
Route at most once to each constraint
Each vertex is part of a constant number of routing paths to constraints
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
All -routing phases combined take O(n) steps
Route at most once to each constraint
Each vertex is part of a constant number of routing paths to constraints
Total: O(n) steps
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Theorem.
We can route locally on the visibility graph by routing on the (non-plane) constrained 6-graph, reaching the destination in O(n) steps.
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Conclusion & Open Problems
There are routing algorithms for constrained graphs
Andre van Renssen

Introduction Routing Conclusion & Open Problems
Conclusion & Open Problems
There are routing algorithms for constrained graphs
Open Problems:
Bound the length of the path of the second algorithm
Local competitive routing algorithm
General deterministic local (competitive) routing algorithm for all constrained -graphs
Andre van Renssen