A Linear-Time Algorithm to Construct a Rectilinear Steiner Minimal Tree for k-External Point Sets

Report
Authors:Richards, D, Department of Computer ScienceUniversity of Virginia Salowe, J, Department of Computer ScienceUniversity of Virginia
Abstract:

A k~extremal point set is a point set on the boundary of a k - sided rectilinear convex hull. Given a k - extrema1 point set of size n, we present an algorithm that computes a rectilinear Steiner minimal tree in time 0(k" rt ). For constant k, this algorithm runs in O(n) time and is asymptotically optimal, and for arbitrary k, the algorithm is the fastest known for this problem.
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Richards, D, and J Salowe. "A Linear-Time Algorithm to Construct a Rectilinear Steiner Minimal Tree for k-External Point Sets." University of Virginia Dept. of Computer Science Tech Report (1990).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1990
Persistent Link:
https://doi.org/10.18130/V33Z2N