文章基本信息

标题：Analysis of two Sweep-line Algorithms for Constructing Spanning Trees and Steiner Trees
本地全文：下载
作者：A. Dumitrescu, C.D. Tóth
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：2007
卷号：13
期号：11
页码：1615-1615
出版社：Graz University of Technology and Know-Center
摘要：We give a tight analysis of an old and popular sweep-line heuristic for constructing a spanning tree of a set of n points in the plane. The algorithm sweeps a vertical line across the input points from left to right, and each point is connected by a straight line segment to the closest point left of (or on) the sweep-line. If W denotes the weight the Euclidean minimum spanning tree (EMST), the spanning tree constructed by the sweep-line algorithm has weight O(W log n), and this bound is asymptotically tight. We then analyze a sweep-line heuristic for constructing a Steiner tree, in which a vertical line is swept across the input points from left to right, and each point is connected by a straight line segment to the closest point on edges or vertices of the current tree (on the left of the sweep line). We show that this algorithm achieves an approximation ratio of O(log n), and describe a class of instances where this ratio is Ω(log n / log log n). Our results give almost complete answers to two old open questions from the 1970s.
关键词：approximation ratio, heuristic, minimum Steiner tree, minimum spanning tree, sweep-line