I know that visibility graph is used to determine the shortest path between two points a mong a set of obstacles in the plane. So in the case that obstacles are triangles, is the maximal number of shortest paths between two points 3? Any hint to prove that?
the number of shortest path between two points
1
$\begingroup$
graph-theory
-
2If you add a flat triangle perpendicular to a straight portion of the path, symmetrically, it doubles the number of shortest paths, so it looks like the maximal number of shortest paths is unbounded. – 2012-04-25
-
0I meant "it increases the number of shortest paths". (doesn't have to be doubled) – 2012-04-26