Fast geometric algorithms

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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Department dc:contributor.department

Computer Science and Applications

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1984

Author dc:creator

• Noga, Mark T.

Chair dc:contributor.committeechair

• Allison, Donald C. S.

Committee members dc:contributor.committeemember

• Roselle, David P.
• Haralick, Robert M.
• Ehrich, Roger W.
• Roach, John W.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/87694

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/87694