Finding shortest s-t paths with a restricted number of orientations
Jillian Nicole Dicker · Summit (Simon Fraser University) · 2012
Finding the path between two points in a polygon which minimizes the Euclidean distance of the path has been studied extensively. In this thesis this problem is modified so that the path contains only a fixed number of orientations, and we wish to find the orientations which minimize the Euclidean length of the path between the two points. A method of finding such a set of orientations is given, and for the case where only two orientation are allowed an algorithm is presented which runs in O(n^2logn) time where n is the number of vertices in the polygon. Finally, previous results concerning the existence of smallest paths - paths which are minimum in both Euclidean distance and link distance - are generalized and it is shown that when the path between two points in a polygon is restricted to only include two orientations, such a path which is smallest always exists.