University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

      The Euclidean arborescence problem

      Thumbnail
      View/Open
      Mazurek_Bradley_W_1996_sec.pdf (5.846Mb)
      Date
      1996
      Author
      Mazurek, Bradley W.
      Type
      Thesis
      Degree Level
      Masters
      Metadata
      Show full item record
      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.
      Degree
      Master of Science (M.Sc.)
      Department
      Computer Science
      Program
      Computer Science
      Supervisor
      Keil, Mark
      Committee
      Srinivasan, Raj; Kusalik, Anthony; Cheston, Grant
      Copyright Date
      1996
      URI
      http://hdl.handle.net/10388/etd-05242012-104112
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy