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 Paths Among 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 v—by 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?
