The Euclidean arborescence problem

The Euclidean arborescence problem involves the creation of rooted trees embedded in the plane using the L2 distance metric. These trees are interesting in that they have a low cost yet offer responsive service from the root to any other vertex. As such, arborescences have their cost compared to that of the minimum spanning tree (MST), and their radius compared to that of the shortest path tree (SPT), which are minimal with respect to cost and radius, respectively. This research examines geometric techniques for constructing such arborescences. The central component to this research is the development of a generalized arborescence algorithm framework. Independent framework modules are used to define a unique arborescence algorithm. Arborescence properties are defined, including metrics to measure the quality of the arborescence relative to the MST cost and the SPT radius. This framework is used to describe four arborescence algorithms: the circle spanning, circle Steiner, unrestricted tangent and restricted tangent arborescence algorithms. Each algorithm is analyzed to determine its computational complexity and space requirements, as well as its theoretical performance with respect to the described quality metrics. However, because theoretical bounds for metrics are not always available or reflective of practice, empirical research was done to determine how each of the algorithms perform in practice. The results of this experimentation look quite favorably on three of the four arborescence algorithms considered. The experimental values for those three have very stable and predictable quality on large point sets, which is well under a two approximation on most metrics.

Name thesis:degree_name

Master of Science (M.Sc.)

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Saskatchewan

Year dc:date.issued

1996

Author dc:creator

• Mazurek, Bradley W.

Advisor dc:contributor.advisor

• Keil, Mark

Committee members dc:contributor.committeemember

• Srinivasan, Raj
• Kusalik, Anthony
• Cheston, Grant

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10388/etd-05242012-104112

OAI identifier oai:identifier

oai:harvest.usask.ca:10388/etd-05242012-104112