The problem of planning a path for a point robot from a source point s
to a destination point d so as to avoid a set of polygonal obstacles
in plane is considered. Using well-known methods, a shortest path from
s to d can be computed with a time complexity of O(n(2)) where n is t
he total number of obstacle vertices. The focus here is in (a) plannin
g paths faster at the expense of setting for suboptimal path lengths a
nd (b) performance analysis of simple and/or well-known suboptimal met
hods. A method that enables a hierarchical implementation of any path
planning algorithm with no increase in the worst-case time complexity,
is presented; this implementation enables fast planning of simple pat
hs. Then methods are presented based on the Voronoi diagrams, trapezoi
dal decomposition and triangulation, which compute (suboptimal) paths
in O(n root log n) time with the preprocessing costs of O(n log n), O(
n(2)) and O(n log n), respectively. Using existing navigational algori
thms for unknown terrains, algorithms that run in O(n log n) time (aft
er preprocessing) and yield suboptimal paths, are presented. For all t
hese algorithms, upper bounds on the path lengths are estimated in ter
ms of the shortest of the obstacles, etc.