Abstract
In this dissertation, we first develop the notion of fixed orientationmetrics with respect to any normed metric, and show that the metric isequivalent to another metric called polygonal Minkowski metric. Then,given n points in the plane,the following geometry proximity problems withrespect to any given fixed orientation metric are discussed : (1)Furthest neighbor searching problem, (2) All furthest neighbors problem,(3) Diameter problem, (4) Maximum spanning tree problem, (5)Furthest-point Voronoi diagram problem, (6) Smallest cnclosing circleproblem, (7) Closest pair problem, (8) All nearest neighbors problem, (9)Minimum spanning tree problem, and (10) Relative neighborhood graphproblem.For the first four problems, we begin by introducing the concept ofbounding hull of a set of points, and show that if this bounding hull isavailable, then the furthest neighbor searching problem can be answered inconstant time. Moreover, with the aid of this bounding hull, the allfurthest neighbors problem, the diameter problem and the maximum spanningtree problem can all be solved in O(n) time.To solve the furthest-point Voronoi diagram problem, we first prove thisproblem is equivalent to the furthest hull line Voronoi diagram problem.Then, we develop both analytic and geometric methods to construct thebisector of two hull lines, and show that the furthest hull line Voronoidiagram can be obtained in O(n) time by using half-planes intersectionmethod. In addition, we show that from the furthest hull line Voronoidiagram, the smallest enclosing circle problem can be solved in O(n) timeand space.A region approach to solve the closest pair problem, the all nearestneighbors problem and the minimum spanning tree problem is presented. Allthese problems can be solved in O(n log n) time and O(n) space. For therelative neighborhood graph problem, we first investigate the behavior ofa lune. Then, again based on the region approach, we propose an O(n log2 n+ m) time algorithm for constructing the relative neighborhood graph wherem is the number of edges in the relative neighborhood graph, n-1 < m