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. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/87694 |
| Date | January 1984 |
| Creators | Noga, Mark T. |
| Contributors | Computer Science and Applications, Allison, Donald C. S., Roselle, David P., Haralick, Robert M., Ehrich, Roger W., Roach, John W. |
| Publisher | Virginia Polytechnic Institute and State University |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation, Text |
| Format | x, 277 leaves, application/pdf, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | OCLC# 11231678 |
Page generated in 0.0027 seconds