SPEAKER: Jit Bose
TITLE: Bounded Leg Shortest Paths
ABSTRACT:
We define a graph whose vertices are points in the plane and edges are segments
weighted by their length to be a geometric graph. Given a geometric graph G and
a pair of vertices x,y in G, we study the following:
1) Determine whether or not there exists a path from x to y where each edge has
length at most c, for some positive constant c.Such a path is called a
c-bounded leg path.
2) How do you preprocess G to quickly determine if there exists a c-bounded leg
path between a given pair of vertices.
3) How do you compute the shortest c-bounded leg path between x and y.
4) How do you preprocess G, such that you can quickly answer c-bounded leg
shortest path queries.