Routing Among Obstacles1
André van Renssen
1Joint work with Prosenjit Bose, Rolf Fagerberg, Matias Korman, and Sander Verdonschot
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André van Renssen
Introduction Routing Conclusion & Open Problems
Introduction
André 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.
André 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 )
André 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 )
André van Renssen
Introduction Routing Conclusion & Open Problems
Obstacles
André van Renssen
Introduction Routing Conclusion & Open Problems
Obstacles
André van Renssen
Introduction Routing Conclusion & Open Problems
Obstacles
André van Renssen
Introduction Routing Conclusion & Open Problems
Obstacles
André 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.
André 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 )
André 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 )
André 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 )
André 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 )
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
▶ Delaunay graphs
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners: ▶ Greedy spanner
▶ Delaunay graphs
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
▶ Greedy spanner ▶ Delaunay graphs ▶ Yao graphs
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
▶ Greedy spanner ▶ Delaunay graphs ▶ Yao graphs
André van Renssen
Introduction Routing Conclusion & Open Problems
Constrained Spanners
Various types of spanners:
▶ Greedy spanner ▶ Delaunay graphs ▶ Yao graphs
▶ Θ-graphs
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
w x
v y
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
w x
v y
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
w x
v y
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
w x
v y
u
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θm -Graph
w x
v y
u
André 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
André van Renssen
Introduction Routing Conclusion & Open Problems
Great! We have a spanner! Now what?
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
t
s
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
t
s
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
▶ Use SSSP algorithm
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
▶ Use SSSP algorithm
▶ Not feasible when the graph is very large
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing
▶ Use SSSP algorithm
▶ Not feasible when the graph is very large ▶ Random walk
André 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
André 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
André 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
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θ6-Graph
v u
s
t
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θ6-Graph
v u
s
t
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θ6-Graph
v u
s
t
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θ6-Graph
t
v u
s
André van Renssen
Introduction Routing Conclusion & Open Problems
The Constrained Θ6-Graph
t
v u
s
André 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
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
u
w
v
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
u
w
v
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing to a Constraint
u
w
z
André van Renssen
Introduction Routing Conclusion & Open Problems
Routing to a Constraint
z
w
u
André 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 shouldn’t cycle
André 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 shouldn’t cycle
Recall: Constraints are edges of the visibility graph
André 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 shouldn’t 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?
André 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 shouldn’t 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
André 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
André 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
André 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
André 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
André 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
André van Renssen
Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
André van Renssen
Introduction Routing Conclusion & Open Problems
Improved Bound
Since the algorithm terminates:
▶ All Θ-routing phases combined take O(n) steps
André 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
André 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
André 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
André 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.
André van Renssen
Introduction Routing Conclusion & Open Problems
Conclusion & Open Problems
▶ There are routing algorithms for constrained graphs
André 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
André van Renssen