The Euclidean arborescence problem

Abstract

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.