Fast geometric algorithms

Abstract

This thesis addresses a number of important problems which fall within the framework of the new discipline of Computational Geometry. The list of topics covered includes sorting and selection, convex hull algorithms, the L₁ hull, determination of the minimum encasing rectangle of a set of points, the Euclidean and L₁ diameter of a set of points, the metric traveling salesman problem, and finding the superrange of starshaped and monotone polygons. The main theme of all our work has been to develop a set of very fast state-of-the-art algorithms which supercede any rivals in terms of speed and ease of implementation. In some cases we have refined existing algorithms; for others we have ·developed new techniques which add to the present database of fast adaptive geometric algorithms. What emerges is a collection of techniques that is successful at merging modern tools developed in analysis of algorithms with those of classical geometry.