0
$\begingroup$

Preface:
There is a net of $N$ almost-straight paths on an aerial map. Some of them intersect with another. At the points of intersection there are possibly a "mis-tie", which is expressed as a number, which is zero if the paths are properly "tied" at the intersection. All those numbers are incorporated into a $N\times N$ matrix $A$, where the cell $A_{ij}$ contains a value of a "mis-tie" at the point of intersection of paths $i$ and $j$. A "mis-tie" is signed, so $A_{ij}=-A{ji}$ (that is, if $i$ is "above" $j$ then $j$ is "below" $i$). There is "nothing" in cells $A_{ij}$ if paths $i$ and $j$ do not intersect.

Problem:
I'd like to minimize (in some sense) the mis-ties by shifting the paths "up" and "down", that is, by adding|subtracting a number from an entire row|column of a matrix $A$ (not affecting the "nothing" cells).

How can I calculate the optimal shifts to all of the paths to minimize the mis-ties? For example, to minimize $\sum_{ij: A_{ij}\neq 0} (A_{ij})^2$ ?

1 Answers 1

1

You want to minimize

$ \sum_{ij}c_{ij}(A_{ij}+s_i-s_j)^2\;, $

where $c_{ij}\in\{0,1\}$, $c_{ij}=c_{ji}$ and $A_{ij}=-A_{ji}$. Setting the derivative with respect to $s_k$ to zero yields

$ \sum_jc_{kj}(A_{kj}+s_k-s_j)-\sum_ic_{ik}(A_{ik}+s_i-s_k)=2\sum_jc_{kj}(A_{kj}+s_k-s_j)=0\;. $

This is a linear system of equations for the $s_k$ that you can solve. If all the $c_{kj}$ were $1$, you could perform the sum over $j$ and calculate the $s_k$ explicitly, but for general $c_{kj}$ I don't see a way to make special use of the binary character of the matrix.

  • 0
    What do you think about solving it iteratively, taking averages along a row|column as an initial $s^1_i$, recalculating $A_{ij} \rightarrow A^1_{ij}$ then taking averages again as $s^2_i$, recalculating $A^1_{ij} \rightarrow A^2_{ij}$ etc. - would it converge to optimal?2012-12-07