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?

  • 2
    $\begingroup$ If 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. $\endgroup$ – galath Apr 25 '12 at 16:10
  • $\begingroup$ I meant "it increases the number of shortest paths". (doesn't have to be doubled) $\endgroup$ – galath Apr 26 '12 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.