Shortest Paths in the Plane with Obstacle Violations We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for k le h. Equivalently, the problem is to find shortest paths that become obstaclefree if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest kpath map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of varTheta (kn) on the size of this map, and show that it can be computed in O(k2n log n) time, where n is the total number of obstacle vertices.

Reliable Hubs for PartiallyDynamic AllPairs Shortest Paths in Directed Graphs We give new partiallydynamic algorithms for the allpairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in widetildeO(mn43logWepsilon) total time (where the edge weights are from 1,W) and explicitly maintains a (1epsilon)approximate distance matrix. For a fixed epsilonu003e0, this is the first deterministic partially dynamic algorithm for allpairs shortest paths in directed graphs, whose update time is o(n2) regardless of the number of edges. Furthermore, we also show how to improve the stateoftheart partially dynamic randomized algorithms for allpairs shortest paths Baswana et al. STOCu002702, Bernstein STOCu002713 from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the widetildeO(cdot) notation).  :121,results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of widetildeO(nd) vertices which hit a shortest path between each pair of vertices, provided it has hoplength Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.