Item Details

Print View

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

Richards, D; Salowe, J
Format
Report
Author
Richards, D
Salowe, J
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
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1990
Published Date
1990
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online