can anybody help me on this algo provided below....................
I need a c++ implementation for the following algorithm.............
Algorithm RST-T
Input: A set of points P = {(xi, yi)}
Output: A rectilinear Steiner tree with all points in P connected
A. Build an RST-T with horizontal trunk
1. Set ymid = median of all yi
2. Set xmin = Min{xi|(xi,ymid)∈P}, xmax = Max{xi|(xi,ymid)∈P}
3. Construct a horizontal trunk from (xmin,ymid) to (xmax, ymid)
4. Set U = {(x,y)|(x,y)∈P and y > ymid}
L = {(x,y)|(x,y)∈P and y <ymid}
5. Sort all points in U according to their x coordinate by
descending order
6. Set Pini=(x,y),where (x,y)∈U and (x,y) minimize |x-xmin|+|x- xmax|
7. Connect Pini to the trunk, going vertical direction first
8. For all the points in U and to the left of Pini, from right to left,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
9. For all the points in U and to the right of Pini, from left to right,
process point p one by one:
Connect p to the neighboring stem or to the trunk depending on
which way is shorter, when we connecting a point to trunk or
stem, we always go vertical direction first.
10. Repeat the procedure from step 5 to step 9, process points in L
B. Build an RST-T with vertical trunk in the similar way to A.
C. Return one tree with shorter total wirelength from two trees built
by step A and step B.

i have developed coding upto step 5 btt after that i am getting confused..............so plz help and if u want to see my work i can post here...............

Wow such a nice problem to solve !!! I solved it now you too try !!! :)

i have developed coding upto step 5 btt after that i am getting confused..............so plz help and if u want to see my work i can post here...............

Yeah, post the work here and a specific question. And mark the other thread solved.

i am attaching two documents ..............now my problem arises from step 6 onwards.how pini is calculated and what the logic behind it and onwards........that means step7,8.............so plz help.............