The Study Of Geometric Algorithms: Color-Spanning Set, Voronoi Diagram And Fréchet Distance

In this thesis, several geometric problems are studied, including geometric problems of color-spanning sets, point location in moving network Voronoi diagram, computation of half-plane Voronoi diagram, a generalization of the Frechet distance in network, and detecting commuting pattern of a trajectory by clustering sub trajectories. The main contributions of this thesis are as follows:Geometric problems of color-spanning sets:given N points with M colors in the plane, choosing M points with distinct colors such that some geometric properties of M points are minimized or maximized. We show the largest closest pair and largest area convex hull are NP-hard, and give 2-approximation algorithm for the latter problem. For the smallest minimum planar spanning tree problem, we show it is NPO-hard. For the maximum diameter problem, an O(N log N) expected time algorithm are provided in this thesis.The problem of moving network Voronoi diagram:given a network, and suppose there are m sites moving along the network edges. The algorithms to compute the dynamic network diagram as sites move such that one can answer the nearest neighbor query efficiently are presented in this thesis. Furthermore, we extend it to k-order dynamic network Voronoi diagram such that one can answer the k nearest neighbor query efficiently. Moreover, the problem to answer the nearest site query when the query point is allowed to move at given speed is studied in this thesis.In order to consider the direction of every site, the so called " half-plane Voronoi diagram" is introduced, which has significant different properties from normal Voronoi diagram. Some basic properties of it are studied, and an algorithm with time O(nlogn) and space O(n) are designed to construct the half-plane Voronoi diagram of O(n) sites with the same direction. For the half-plane Voronoi dagram of sites with arbitrary direction, an O(n2\ogn) time and O(n2)space algorithm are provided in this thesis.Frechet distance is an important measurement of the similarity between two curves. We extend it to network distance, and design algorithm to compute network Frechet distance. K. Buchin etc studied the problem:Detecting commuting patterns by clustering subtrajectories based on discrete Frechet distance. For that problem, an improved algorithm with less time complexity but the same space complexity is given in this thesis.