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.