| Problems involving navigation on surfaces in {dollar}IR{dollar}3 arise in applications such as robotics, terrain navigation, medical imaging and low-altitude flight simulation. An important problem is that of computing the shortest path between two points along a given polyhedral surface. In most applications, a simple, efficient, algorithm for computing an approximate shortest path is preferable to an expensive algorithm that computes the exact path. The first result of this thesis is an efficient approximation algorithm for the case when the surface is the boundary of a convex polytope. Our second result is an efficient approximation algorithm for the case when the surface is a nonconvex polyhedron. The nonconvex case is solved using techniques very different from the convex case.; The polygonal chain simplification problem involves approximating a given polygonal curve by a coarser curve. The goal is to reduce the complexity of the representation as much as possible while still staying geometrically close to the original curve. This problem is important in applications such as graphics, digital image processing, geographic information systems, and cartography, where polygonal chains are used to represent the boundaries of planar objects. Our third result is an efficient algorithm which we obtain for a version of this problem by exploiting the geometry of the problem better than in previous approaches.; Many geometric optimization problems can either be posed as a graph optimization problem or can be solved by reducing to a graph optimization problem. A good example of such a problem is the Euclidean min-cost perfect matching problem which arises in operations research, pattern recognition, statistics, and VLSI. The approach of solving the geometric problem using an algorithm for the corresponding graph problem is usually wasteful because it ignores the geometric structure. Hence, researchers in computational geometry have looked for more 'geometric' approaches. Pursuing a similar goal, we obtain our final result, which is an algorithm for min-cost perfect matching of a set of points in the plane that is significantly faster than previous algorithms. |
