# CS代考程序代写 algorithm Routing Among Obstacles1

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

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

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

The Constrained Θm -Graph

w x

v y

u

André van Renssen

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