We have N points in R^2, and a list of pairs of points that must be connected by

Question

We have N points in R^2, and a list of pairs of points that must be connected by links. The positions of some of the N points are fixed; our task is to determine the positions of the remaining points. The objective is to place the points so that some measure of the total interconnection length of the links is minimized. As an example application, we can think of the points as locations of plants or warehouses of a company, and the links as the routes over which goods must be shipped. The goal is to find locations that minimize the total transportation cost. In another application, the points represent the position of modules or cells on an integrated circuit, and the links represent wires that connect pairs of cells. Here the goal might be to place the cells in such a way that the total length of wire used to interconnect the cells is minimized. The problem can be described in terms of a graph with N nodes, representing the N points. With each free node we associate a variable (u_i, v_i) epsilon R^2, which represents its location or position. In this problem we will consider the example shown in the figure below. Here we have 3 free points with coordinates (u_1, v_1), (u_2, v_2), (u_3, v_3). We have 4 fixed points, with coordinates (-1, 0), (0.5, 1), (0, -1), and (1, 0.5). There are 7 links, with lengths l_1, l_2, ....l_7. We are interested in finding the coordinates (u_1, v_1), (u_2, v_2) and (u_3, v_3) that minimize the total squared length l^2_1 +l^2_2 + l^2_3 + l^2_4 + l^2_5 + l^2_6 + l^2_7. Formulate this problem as a least squares problem minimize ||Ax - b||^2 where the 6-vector x contains the six variables u_1, u_2, u_3, v_1, v_2, v_3. Give the coefficient matrix A and the vector b. Show that you can also obtain the optimal coordinates by solving two smaller least squares problems minimize ||A vector u - b vector||^2, minimize ||A cap v - b cap ||^2, where u = (u_1, u-2, u-3) and v = (v_1, v_2, v_3). Give the coefficient matrices A vector, A cap and the vectors b vector and b cap. What is the relation between A vector and A cap? Solve the least squares problems derived in part (a) or (b) using MATLAB.

Explanation / Answer

Answer: See the solution below:

a) Given points are: (-1,0), (0.5,1), (0,-1), (1,0.5)

Points to find out are: (u1,v1), (u2,v2), (u3,v3)

x is (u1, u2, u3, v1, v2, v3).

Distances are:

l1 = ((u1-u2)^2+(v1-v2)^2)^1/2 -> l1^2 = ((u1-u2)^2+(v1-v2)^2)

l2 = ((u1-u3)^2+(v1-v3)^2)^1/2 -> l2^2 = ((u1-u3)^2+(v1-v3)^2)

l3 = ((-1-u1)^2+(0-v1)^2)^1/2 -> l3^2 = ((-1-u1)^2+(0-v1)^2)

l4 = ((u2-0.5)^2+(v2-1)^2)^1/2 -> l4^2 = ((u2-0.5)^2+(v2-1)^2)

l5 = ((0-u3)^2+(-1-v3)^2)^1/2 -> l5^2 = ((0-u3)^2+(-1-v3)^2)

l6 = ((u3-1)^2+(v3-0.5)^2)^1/2 -> l6^2 = ((u3-1)^2+(v3-0.5)^2)

l7 = ((u2-1)^2+(v2-0.5)^2)^1/2 -> l7^2 = ((u2-1)^2+(v2-0.5)^2)

sum of squared distances: l1^2+l2^2+l3^2+l4^2+l5^2+l6^2+l7^2

= [(u1-u2)^2+(v1-v2)^2] + [(u1-u3)^2+(v1-v3)^2] + [(-1-u1)^2+(0-v1)^2] + [(u2-0.5)^2+(v2-1)^2] + [(0-u3)^2+(-1-v3)^2] + [(u3-1)^2+(v3-0.5)^2] + [(u2-1)^2+(v2-0.5)^2]

= [u1^2+u2^2-2u1u2+v1^2+v2^2-2v1v2]+[u1^2+u3^2-2u1u3+v1^2+v3^2-2v1v3]+[1+u1^2-2u1+v1^2]+[u2^2+0.25-u2+v2^2+1-2v2] + [u3^2+1+v3^2+2v3]+[u3^2+1-2u3+v3^2+0.25-v3]+[u2^2+1-2u2+v2^2+1-v2]

= 3u1^2+3u2^2-2u1u2+3v1^2+3v2^2-2v1v2+3u3^2-2u1u3+3v3^2-2v1v3+6-2u1-u2-2v2+2v3-2u3-v3-2u2-v2

= 3u1^2+3u2^2+3u3^2+3v1^2+3v2^2+3v3^2-2u1u2-2v1v2-2u1u3-2v1v3+6+2u1-3u2-2u3-3v2+v3

= (3u1^2-2u1u2+2u1)+(3u2^2-3u2)+(3u3^2-2u1u3-2u3)+(3v1^2-2v1v2)+(3v2^2-3v2)+(3v3^2-2v1v3+v3)+6

= (3u1-2u2+2)u1+(3u2-3)u2+(3u3-2u1-2)u3+(3v1-2v2)v1+(3v2-3)v2+(3v3-2v1+1)v3+6

=> [(3u1-2u2+2)

    (3u2-3)

    (3u3-2u1-2)

    (3v1-2v2)

    (3v2-3)

   (3v3-2v1+1)]' [u1 u2 u3 v1 v2 v3]' = -6

Hence A = [(3u1-2u2+2)

    (3u2-3)

    (3u3-2u1-2)

    (3v1-2v2)

    (3v2-3)

   (3v3-2v1+1)]'

b = -6

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.