| Over the past few years, the advent of computer science has resulted in the development of computational geometry, a field of mathematics that has infused discrete geometry with a new interest. Optimal results in discrete geometry, as well as the properties that imply them, are extremely important in computational geometry, and are valuable tools in the creation of mathematical algorithms. One of the most extensively studied problems in computational geometry is one of efficiently avoiding obstacles in a packing while traversing a strip in the plane. We address many variations of this problem: (1) the obstacles are closed disks which form a covering of the plane and we are allowed to travel only through double-covered regions or only along circle boundaries, (2) the obstacles are closed unit squares and we are allowed to travel only through double-covered regions, (3) the obstacles are copies of an arbitrary n-dimensional convex region (n ∈ {lcub}2, 3{rcub}) and we are allowed to travel only through double-covered regions, and (4) the obstacles are convex polygons which tile the plane in an edge-to-edge manner, and we are allowed to travel only along boundary segments of the tiling. Each of these problems has further variations where we specify whether we are operating with map, where the placement of all circles or polygons is known to the traveller before the journey begins, or without map, where information about a given circle or polygon is revealed only upon the traveller's contact with it. We specify lower bounds for the best possible path constants, and provide reasonably efficient algorithms for these variations, as well as the path constants that result from them. We conclude by stating a few remaining open problems suggested by the results. |
