This Applet is a demonstration of the factor 2 approximation algoirthm for Rectilinear Steiner Arborescence (RSA), as proposed by Sailesh K. Rao, P. Sadayappan, Frank K. Hwang and Peter W. Shor in "The rectilinear steiner arborescence problem", Algorithmica, 1992.
The Rectilinear Steiner Arborescence problem is formulated as follows:
Input: A set of points in E2, in the first quadrant.
Output: A set of axis-aligned edges that together connect each given point to the origin, such that the sum of the edge lengths is minimum. In addition, the path from origin to any point must move in the positive x (left to right) or the poitive y (bottom to top) direction. The direction requirement is what distinguishes an aborescence from a tree.
The approximation algorithm goes as follows:
Notation: 1. Let (px, py) be the coordinate of point p. 2. Let cover(p,q) = (min(px,qx),min(py,qy)) for points p, q. 3. |p| = px + py Algorithm: 1. Let S be the set of given points, plus the origin. 2. while(S has at least 2 elements) 2.1 From the elements of S, let p, q be such that |cover(p,q)| is maximum. 2.3 Output/Draw the edges from cover(p,q) to p, and cover(p,q) to q. 2.4 Remove p and q from S 2.5 Add cover(p,q) to S.
In the paper, the authors suggested an O(n log(n)) implementation, however this applet is using a naive O(n2) implementation. For details of the n log(n) algorithm, please consult the paper. You can find a proof of the approximation guarantee (extracted and refined from the paper) here.
How to operate this applet
1. To add points, simply click on the first quadrant. As points are added, the new RSA is (re)computed and displayed.
2. To reset the applet and remove all points, click on a location not in the first quadrant. i.e., click on the left of the vertical black line, or below the horizontal black line.