Kevin Brown Geometric Transforms for Fast Geometric Algorithms Degree Type: Ph.D. in Computer Science Advisor(s): Michael Shamos Graduated: May 1980 Abstract: Many computational problems are inherently geometrical in nature. For example, cluster analysis involves construction of convex hulls of sets of points, LSI artwork analysis requires a test for intersection of sets of line segments, computer graphics involves hidden line elimination, and even linear programming can be expressed in terms of intersection of half-spaces. As larger geometric problems are solved on the computer, the need grows for faster algorithms to solve them. The topic of this thesis is the use of geometric transforms as algorithmic tools for constructing fast geometric algorithms. We describe several geometric problems whose solutions illustrate the use of geometric transforms. These include fast algorithms for intersecting half-spaces, constructing Voronoi diagrams, and computing the Euclidean diameter of a set of points. For each of the major transforms we include a set of heuristics to enable the reader to use geometric transforms to solve his own problems.
