Project Report CS239: Computational Geometry

Optimal Packet Routing Scheme with Multiple Sources and Multiple Destinations

Submitted by

(403-134-387)
Winter 2004

Input / Problem
The idea of the problem originates from the need of online companies like amazon, netflix, etc, to send the merchandize purchased by customers. The customers are located at different places. How these packets are routed so as to minimize the cost is a big problem. Most of the times these stores have multiple distribution centers or outlets from where the demand can be met. Thus the problem takes the shape of multiple source, multiple, multiple destinations.

Given
‘n’ Source points (Distribution centers), and ‘m’ destination/consumer points. Location of the distribution and destination points described in their (x,y) co-ordinates. The measure of cost is the distance metric (length of the route).

Output
The output of the problem would be, which distribution center would serve which destination points and how the packet would be routed to minimize cost. Note: If the routes are represented as a graph then the graph would be a disconnected graph, depending on what destination nodes are served by which distribution center node.

What is known?
The general case of this problem, without any restrictions, can be modeled as Steiner Tree problem. It is a well known problem and its computation has been shown to be NPHard, by Garey, Graham and Johnson (1976).

Approach
In this analysis, I am considering the following 3 problems. 1. Multiple source Minimum Spanning Tree (M ST) 2. Multiple source Steiner Tree 3. Multiple source Traveling Salesman Problem (TSP) Multiple source TSP problem refers to the case where we have only one vehicle per distribution center, and it has to cover all the customers or destination points. The other two problems refer to the case where we have unlimited number of resources (in terms of vehicles and man power needed to transmit them) and the path followed can be forked. The difference between the first two cases is where the path can be forked. In 1st case, it can be forked at a destination point only. While in 2nd case it can be forked at any point. All these problems are considered in Euclidean space. In this project I am targeting the first 2 problems. I have solved the first problem deterministically in O(nlogn) time. And I am presenting a heuristic for the 2nd problem. The heuristic take MST as a starting point and iteratively improves the solution.

In the subsequent analysis, the number of vertices V is equal to sum of number of sources ‘n’, and number of destination/consumers ‘m’.

Multiple Sources Euclidean Minimum Spanning Tree Algorithm
The algorithm works the same way as a standard Euclidean M inimum Spanning Tree (EMSpT). The only difference is in joining the spanning trees, as in Kruskal’s algorithm. All the nodes connected to a source, are assigned the source number of that source. As shown in the figure below. A number ‘0’ indicates that the nodes are not connected to any source. Only 2 types of merging is allowed, 1. Between two spanning trees, with number ‘0’. The new spanning tree also has ID ‘0’. 2. Between two spanning trees, one numbered ‘0’ and other has a source ID. The nodes of the merged spanning tree take the ID of the source. Spanning trees with different source IDs are not merged. Algorithm

1. Find the Delaunay triangulation for a given set V. 2. Assign ID ‘0’ to all the nodes, and source IDs to respective source nodes. 3. Find the Minimum Spanning Tree, using Kruskal’s Algorithm and using the above rules for merging. (See figure 1 below).

(a) (b) Figure 1. (a) Partial solution for EMSpT, (b) Showing merging of two different subgraphs, and assignment of ID to subgraphs. Optimality of this algorithm follows from the proof of Kruskal’s Algorithm. Complexity The complexity of the algorithm is O(VlogV). Calculating the Delaunay Triangulation takes O(VlogV) time. And the Delaunay Triangulation represent a planar graph, which can have 3V – 6, edges in the worst case. So the number of edges is O(V). So the Kruskal’s algorithm also takes O(VlogV) time. So the overall time complexity is O(VlogV).

Multiple source Euclidean Minimum Steiner Trees
Background Details about Steiner Tree First I will define the Euclidean Steiner tree problem. Given a set of fixed points V={v1,v2, ... ,vn} in the Euclidean plane, called terminals, and asks for the shortest straight-line graph spanning V. The solution takes the form of a tree, called a Euclidean Minimum Steiner tree (EMStT). Contrary to the minimum spanning tree problem, connections in EMStT's are not required to be between the terminals only. Additional intersections, called Steiner points, can be introduced to obtain shorter spanning networks. The distance metric, that I will be using is L2 metric, i.e. Euclidean Distance. Where the distance between two points u = (ux, uy) and v = (vx, vy), is defined as

d (u , v) = (u x − vx ) 2 + ( u y − v y ) 2
Euclidean minimum Steiner tree can also be defined for other metrics also. A lot of work has been in the area of Rectilinear minimum Steiner trees, where the distance metric is L1. Euclidean Steiner tree problem applications span a wide range, from design of VLSI circuits, to modeling the evolution of species in biology to modeling soap films for grids of wires; from the design of collections of data to the design of heating or air-conditioning systems in buildings; and from the creation of oil and gas pipelines to the creation of communication networks, electrical power distribution networks, road and railway lines. The Euclidean mimimum spanning tree (EMSpT) can be used as an approximate Steiner tree. The supremum (over all terminal sets V) of the ratio between the minimum spanning tree length and Steiner minimum tree length is denoted as Steiner ratio. It can be proved [2] that the Steiner ratio ? for the Euclidean problem satisfies the following formula:

ρ = sup

V ⊂R2

w( EMSpT (V )) 2 = ≈ 1.1547 w( EMStT (V )) 3

So, EMSpT length does not exceed that of an EMStT by more than 15.47% in the worst case. Therefore, the EMSpT is generally taken a standard against which other approximation algorithms or heuristics are compared, also it is often the starting point of many heuristics and approximation algorithms, since it atleast guarantees that you are not off from the optimal by more than 15.47%. Equilateral triangles represent the best improvement where the gain of EMStT over EMSpT is 15.47%.

Next, I mention some properties of Steiner Trees, which are used in this report. It is known [2, 6], that the Steiner minimum trees have the following properties: • All Steiner points are incident with exactly 3 edges making 120° with each other (i.e. they have degree 3 with respect to the edges used in the tree). • ESMT's for n terminals have at most n- 2 Steiner points. • Every non Steiner point has degree 1 or 2. It can also have degree three, only when all the 3 edges make angle of 120°, among themselves. • No point in Steiner tree, (Steiner and non-Steiner) have degree more than 3. Another interesting property, that we use in our solution and which most other Steiner tree solutions use, is based on the answer of the following question. Q. Given three points in the plane, find a fourth point such that the sum of its distances to the three given points is a minimum. This problem was solved by Torricelli in 1640, which said “Circles circumscribing the equilateral triangles constructed on the sides of and outside the triangle ? (P1,P2,P3) intersect at the point X that is sought, called the Torricelli point.” (Figure 1 (a)). Further, the lines from the Torricelli point to the given points Pi subtend angles of 120o. [3] Simpson, in "Doctrine and Application of Fluxions", 1750, proved that the three lines joining the outside vertices of the equilateral triangles defined above to the opposite vertices of the given triangle intersect at the Torricelli point. The three lines are called Simpson lines. (Figure 2 (b)) [3]

(a) (b) Figure 2 Different methods to obtain Torricelli point. X is the Torricelli point for triangle P1P2P3.

Heinen, in 1834 proved that the lengths of the three Simpson lines are equal and equal to the minimum sum of distances. Heinen also proved that for a triangle in which one angle is greater than or equal to 120o, the vertex of this angle is the minimizing point. [3] Figure 3 below shows another method to calculate the Torricelli point. In the figure, a, b and c are the given vertices. We construct an equilateral triangle ? abd, and circumscribe it. The Torricelli point, is the point of intersection of line segment cd and the circumcircle of equilateral triangle ? abd. And the line cd is also the Simpson line.

Figure 3. Another method to obtain Torricelli point S. These properties would be used to find the Torricelli point in the proposed algorithm. Based on the above discussion, if number of vertices is 3, i.e. |V| = 3 we can directly construct the EMStT. 1. If the maximum angle is less than 120o, then the Torricelli point is the Steiner point, and the EMStT consists of 3 edges, with the Steiner point joined to the other 3 vertices. 2. If the maximum angle in the triangle is more than 120o, then the EMStT is the graph with 2 edges, with the vertex with maximum angle, joined to the other 2 vertices. Algorithm to obtain Multiple source Euclidean Minimum Steiner Trees First step is to partition the 2D plane into separate regions, so as to decide what destination points would be served by which distribution center. For the partition of the space, I using the nodes partition obtained by running Multiple source MST problem (described earlier). The reasoning behind this is that, if a point belongs to a particular spanning tree in Multiple source EMSpT, then in the Multiple source EMStT that point will belong to EMStT for that source only. Lets say a node ‘a’ from EMSpT of source x, joins EMStT of source y. Then the length of the edge that will join it to another node in EMStT of source y, will be more than edge with which it was joined in EMSpT of source x. As otherwise in the first place when constructing Multiple source EMSpT, it would have joined EMSpT of source y. Also the point closest to node ‘a’ in EMStT of source y would be a terminal node not a Steiner node, as Steiner points are with in the triangle formed by the three nodes they are joining, such that they subtend 120o , on all the edges of the triangle.

Thus any point outside this triangle will be closer to one of the nodes linked to the Steiner point, then to the Steiner point. Next I describe the reasoning to choose Delaunay Triangulation As mentioned earlier, equilateral triangles, represent the case for the best improvement in cost of EMStT over EMSpT. All angles in equilateral triangles are equal to 60° and they maximize the minimal angle. Since, by [4], any Delaunay triangulation of V maximizes the minimal angle over all triangulations of V, Delaunay triangulation is taken as the starting point. We use Delaunay triangulation, to generate MST, but we will get a better initial approximation if we replace each of the triangles with their EMStTs. EMStTs for triangles in which one of the angle is more than 120o is 2 edge graph with edges from the vertex of the angle to other 2 vertices. And for those triangles where all angles are less than 120o, we can find EMStT using method described earlier. Next I describe my algorithm for constructing EMStT. This algorithm would be applied to each of the partitioned sets. Here V refers to the number of nodes in the partition being considered. 1. Find the Delaunay triangulation for a given set V (Figure 4(a)) 2. For all triangles with angle less than 120°, replace the triangle with EMStT of triangle vertices. i.e a Steiner point will be added to each of the triangles with all the angles less than 120°, and 3 edges joining the Steiner point to the 3 vertices of the triangle and we are removing the edges of the triangle (Delaunay Edges). (Figure 4(b), (c)). One triangle where all the angles are not less than 120o doesn’t have a Steiner point inside the triangle. 3. Determine the Euclidean minimum spanning tree EMSpT for a graph found by Step 2. (Figure 4(d)) 4. Scan the resultant graph for Steiner points with degree 1 and 2 a. For each Steiner points with degree one, remove the Steiner point along with the edge connecting it. b. For each Steiner points with degree 2, remove the Steiner point and along with the two edges, and add an edge between the vertices, to which the Steiner point was connected The result of this operation is shown in Figure 4(e). 5. Start scanning the resultant spanning tree from an end (a leaf). a. For every angle of every node that is less than 120°, generate EMStT, for the nodes forming the angle. b. Remove the edges that formed the angle. Figure 4(f) shows the result of first scan through the spanning graph and 4(g) shows the result of 2nd scan. In the 2n d scan the Steiner points, only move slightly in their vicinity. The new Steiner points have to be found as all the angles at the Steiner point (a), is not 120o, due to the new Steiner point (b). Now when a new Steiner point is found for (a), this will change the angle at (b), and we have to find a new Steiner point for (b). 6. Repeat the step 5 until all the angles are more than or equal to 120°, or amount of improvement in cost reduces below the threshold

(a) Delaunay Triangulation

(b) Steiner Points in qualifying Triangles

(c) Edges added associated with Steiner Pts

(d) MST for graph in (c)

(e) Removal of unnecessary Steiner points

(f) First scan through the graph

(g) Second scan through the graph Figure 4. Different steps in Algorithm to find Euclidean Minimum Steiner Tree

Claim After first iteration of step 5, the resultant Steiner tree will have the same number of Steiner points as there will be in optimal Steiner tree. Claim is based on the way the algorithm works. As subsequent iterations of step 5 only move the Steiner points in their vicinity. No new Steiner points are created. The refinement in Steiner Tree is local. The decrease in cost of the Steiner tree relative to the cost of Steiner tree of previous iteration will diminish at every iteration. And eventually it will converge to the optimal Steiner tree. The algorithm guarantees that the optimal solution would be reached, as at every iteration we are decreasing cost. The issue is how well it converges? Time Complexity If |V| = n, then the Delaunay triangulation can be constructed in O(n log n) time. The expected number of triangles created is at most 9n+1 [4] and thus Step 2 needs O(n) time. Step 3 needs O(n log n) time to construct EMSpT. Step 4 would take O(n) time, as we just need to scan the spanning tree once or just look at all the Steiner points. Time complexity of each iteration of step 5 is O(n). As the number of angles that have to be considered is O(n), also at each step constant amount of work is required. Actual complexity will depend on how many times the loop is executed. In order to determine how many times the loop is executed, we can set a threshold. If the percentage gain over the previous iteration falls below the threshold, then we stop iterating the step 5. To determine, how well does it perform in actual applications we need to do simulations to test its performance. I expect it to be within O(n). So the time complexity should not be worse then O(n2). Future Work We need to perform computational tests for the proposed heuristic. And the parameters that will have to be measured will be amount of time taken by the proposed heuristic to converge and also how much beyond the optimal it is after every scan of the Steiner tree. We would also need to compare the results with other algorithms and heuristics. One of the most common program which finds the optimal solution for Steiner Tree is geosteiner [5,6], it has the best performance among Steiner tree programs which computes optimal Steiner tree. Another problem that I wanted to consider was to change the cost dependant on the traffic on the path, not just the distance metric, i.e. the number of packets transmitted on a particular path.

Reference: [1] M. R. Garey, R. L. Graham and D. S. Johnson, Some NP-complete geometric problems, Eighth Annual Symposium of Theory of Computing, pp 10-22 (May 1976). [2] Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam, 1992. [3] http://www.ces.clemson.edu/~pmdrn/Dearing/location/totalcost.pdf [4] De Berg, M., van Kreveld, M., Overmars, M. and Schwarzkopf, Computational

Geometry:Algorithms and Applications . Springer-Verlag, Berlin, 2000 (2nd rev. ed.).
[5] http://www.diku.dk/geosteiner/ [6] Winter P., Zachariasen M., Euclidean Steiner Minimum Trees: An Improved Exact Algorithm, Networks, 1997