I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying justify that using the visibility graph algorithm on spherical polygons transformed with the Gnomonic Projection to a linear plane will result in the shortest path, using great circle distance, between two points on the sphere's circle. To do so, I need to understand what assumptions the visibility graph needs to be valid, so I can see if those are still true for this mapping.On page 612 of Discrete and Computation Geometry, Mitchell states:It is easy to show that an locally optimal s-t path must on the  visibility graph VG(P)Referring to the fact that a shortest path between two points, navigating around polygonal obstacles, can be found by creating a visibility graph and then searching that visibility graph using an algorithm like A*.He however, does not explicitly state how we know that this path is in the visibility graph.The paper most people cite for the original Visibility Graph algorithm is An Algorithm for Planning Collision-Free PathsAmong Polyhedral Obstacle from 1979, stating:The shortest collision-free path from S to G on the plane is the  shortest path in the VGRAPH from the node corresponding to S to that  corresponding to G when the euclidean metric is used on the links. We  will call this method for finding collision-free paths for a point by  finding the shortest path in a visibility graph the VGRAPH algorithm.  This method was used for navigating SHAKEY [8], an early robot  vehicle, and is also described in some detail in Ignat'yev [5].They however, again fail to say how they know this is true. The SHAKEY paper also does not mention any proof.Now in Chapter 15 of Computational Geometry: Algorithms and Applications, titled Visibility Graphs Finding the Shortest Route, they give this proof for why they shortest path should consist entirely of endpoints of the obstacles, implying that it will be in the visibility graph:Lemma 15.1 Any shortest path between pstart and pgoal among a set S of  disjoint polygonal obstacles is a polygonal path whose inner vertices  are vertices of S.Proof. Suppose for a contradiction that a shortest  path  is not polygonal. Since the obstacles are polygonal, this means  there is a point p on  that lies in the interior of the free space  with the property that no line segment containing p is contained in .  Since p is in the interior of the free space, there is a disc of  positive radius centered at p that is completely contained in the free  space. But then the part of  inside the disc, which is not a straight  line segment, can be shortened by replacing it with the segment  connecting the point where it enters the disc to the point where it  leaves the disc. This contradicts the optimality of , since any  shortest path must be locally shortest, that is, any subpath  connecting points q and r on the path must be the shortest path from q  to r. Now consider a vertex v of . It cannot lie in the interior of  the free space: then there would be a disc centered at p that is  completely in the free space, and we could replace the subpath of   inside the disc which turns at vby a straight line segment which is  shorter. Similarly, v cannot lie in the relative interior of an  obstacle edge: then there would be a disc centered at v such that half  of the disc is contained in the free space, which again implies that  we can replace the subpath inside the disc with a straight line  segment. The only possibility left is that v is an obstacle vertex.They however, don't give a citation for this proof. Is there a previous version of this proof, or is this the original?Are there other ways to writing this proof?
What is the proof that visibility graphs can be used to compute the shortest path?
cg.comp geom;shortest path