Steiner Minimal Trees with One Polygonal Obstacle

Steiner Minimal Trees with One Polygonal Obstacle

0.00 Avg rating0 Votes
Article ID: iaor20121023
Volume: 29
Issue: 4
Start Page Number: 638
End Page Number: 648
Publication Date: Apr 2001
Journal: Algorithmica
Authors: ,
Keywords: Steiner problem, topology, trees
Abstract:

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n 2 +nlog 2 k) time. Further, if ω is nonconvex, we then show that O(n 2 +nklog k) time is required.

Reviews

Required fields are marked *. Your email address will not be published.