Improved Datastructures Compact Datastructure for Zones
x1-x2<=4
x2-x1<=10
x3-x1<=2
x2-x3<=2
x0-x1<=3
x3-x0<=5
x1
x2
x3
x0
-4
10
2
2
5
3
x1
x2
x3
x0
-4
4
2
2
5
3
x1
x2
x3
x0
-4
2
2
3
3
-2
-2
1
Shortest
Path
Closure
O(n^3)
Shortest
Path
Reduction
O(n^3)
3
Canonical wrt =
Space worst O(n^2)
practice O(n)
Previous slide
Next slide
Back to first slide
View graphic version