@article {Conn1997,
title = {A counterexample to the Alexopoulos-Griffin path planning algorithm},
journal = {Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on},
volume = {27},
number = {4},
year = {1997},
month = {August},
pages = {721 {\textendash}723},
abstract = {The planar stationary-obstacle path-planning problem for polygonal obstacles has been correctly and completely solved by T. Lozano-Perez and M. Wesley (1979), i.e., a global, optimal algorithm was provided which requires O( mu;2log mu;) computation time, where mu; is the number of obstacle-faces in the scene. That algorithm is known as the VGRAPH algorithm. Two variants of VGRAPH have been developed to solve the same problem in O( mu;2) computation time. Our paper discusses a recent algorithm proposed by C. Alexopoulos and P.M. Griffin (1992), called V*GRAPH, which also claims to provide an optimal solution. We demonstrate by counter-example that V*GRAPH is neither global nor optimal},
keywords = {Alexopoulos-Griffin path planning algorithm, computational complexity, optimal algorithm, path planning, polygonal obstacles, VGRAPH algorithm},
author = {Robert A. Conn and J. Elenes and Moshe Kam}
}