Smallest paths in polygons
Kenneth M McDonald · Summit (Simon Fraser University) · 1989
A rectilinear path is a path composed only of horizontal and vertical line segments.Such paths may be constrained by requiring that they lie only within certain areas.One way of doing this is to require that a rectilinear path be entirely contained within a given simple polygon.We show that between any two non-vertex points in any simple polygon, there is a rectilinear path entirely contained within the polygon, which simultaneously possesses the properties that it is of no greater length and has no more bends than any other rectilinear path between the two given points and lying within the given polygon.Such a path is termed a smallest path.We further give an O(n log n) sequential algorithm to calculate the length and number of bends of a smallest path between two given points in any simple polygon, where n is the number of vertices of the polygon, and also develop parallel algorithms to do the same task, which run in 0(log2 n) time using n/log n processors, or in O(1og n log log n) time using n processors.Finally, we consider the case where rather than being restricted to the inside of a simple polygon, we restrict our rectilinear paths to lie outside a set of rectlinear objects, and given an 0(n3) seqential algorithm to determine if a smallest path exists in such an environment, where n is the total number of comers in the set of rectilinear obstacles.. .