<p>I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113.</p>

<blockquote>
  <p>With the above result it is immediate to realize that the shortest
  path problem with line segments as obstacles can be solved by first
  constructing the graph G=(V,E), called visibility graph, where V
  consists of the two distinguished points and the set of 2N endpoints
  of the given N line segments, E is the set of edges each of which
  connects two vertices i and j of V without intersecting any obstacle
  except possibly at the endpoints (i and j are visible according to Definition 4.2); and the weight
  associated with each edge (i,j) of E is the Euclidean distance between
  points i and j; and then applying a well known shortest path algorithm
  to G.</p>
</blockquote>

<p>However this is only for with line segments as obstacles, not polygons as obstacles.</p>

CC BY-SA 3.0
2016-08-05T00:35:12.100Z
Polygonal obstacles are no different from the sides of the polygons (which are line segments) as obstacles.
David Eppstein
CC BY-SA 3.0
2016-08-05T00:36:50.197Z
He limits it to disjoint line segments, which excludes polygons, right?
saul.shanabrook
CC BY-SA 3.0
2016-08-04T19:03:43.173Z
2016-08-04T19:12:40.750Z
2016-08-04T19:12:40.750Z
saul.shanabrook
<p>I am trying to understand what the proof is that constructing a <a href="https://en.wikipedia.org/wiki/Visibility_graph" rel="nofollow">visibility graph</a> 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 <a href="http://mathworld.wolfram.com/GnomonicProjection.html" rel="nofollow">Gnomonic Projection</a> 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.</p>

<p>On page 612 of Discrete and Computation Geometry, Mitchell states:</p>

<blockquote>
  <p>It is easy to show that an locally optimal s-t path must on the
  visibility graph VG(P)</p>
</blockquote>

<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*.</p>

<p>He however, does not explicitly state how we know that this path is in the visibility graph.</p>

<p>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:</p>

<blockquote>
  <p>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].</p>
</blockquote>

<p>They however, again fail to say how they know this is true. The SHAKEY paper also does not mention any proof.</p>

<p>Now in <a href="http://www.springer.com/cda/content/document/cda_downloaddocument/9783540779735-c1.pdf?SGWID=0-0-45-532201-p173799863" rel="nofollow">Chapter 15 of Computational Geometry: Algorithms and Applications, titled "Visibility Graphs Finding the Shortest Route"</a>, 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:</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>They however, don't give a citation for this proof. Is there a previous version of this proof, or is this the original?</p>

<p>Are there other ways to writing this proof?</p>

<cg.comp-geom><shortest-path>
What is the proof that visibility graphs can be used to compute the shortest path?
saul.shanabrook
# What is the proof that visibility graphs can be used to compute the shortest path?

(Asked by: username_0 on 2016-08-04)

I am trying to understand what the proof is that constructing a [visibility graph](https://en.wikipedia.org/wiki/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](http://mathworld.wolfram.com/GnomonicProjection.html) 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"](http://www.springer.com/cda/content/document/cda_downloaddocument/9783540779735-c1.pdf?SGWID=0-0-45-532201-p173799863), 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?

**Tags:** cg.comp-geom, shortest-path


---

## 1 answers

### Answer by username_0 on 2016-08-04. Score: 2

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113.

> With the above result it is immediate to realize that the shortest
> path problem with line segments as obstacles can be solved by first
> constructing the graph G=(V,E), called visibility graph, where V
> consists of the two distinguished points and the set of 2N endpoints
> of the given N line segments, E is the set of edges each of which
> connects two vertices i and j of V without intersecting any obstacle
> except possibly at the endpoints (i and j are visible according to Definition 4.2); and the weight
> associated with each edge (i,j) of E is the Euclidean distance between
> points i and j; and then applying a well known shortest path algorithm
> to G.

However this is only for with line segments as obstacles, not polygons as obstacles.

> **Comments:**
> **username_1**: Polygonal obstacles are no different from the sides of the polygons (which are line segments) as obstacles.  
> **username_0**: He limits it to disjoint line segments, which excludes polygons, right?  

---

