1
$\begingroup$

I have an upper row of $N$ equally spaced 'units' and a lower row of $N$ equally spaced 'units'. I would like to connect any of the upper row of units to the lower units via orthogonal connectors (consisting of horizonal and vertical line segments) such that although a horizontal and a vertical line segment, e.g. connecting $(3, 12)$ and $(4, 10)$, are allowed to intersect as shown below,

Orthogonal connectors between row of equally spaced units

a horizontal line segment may not overlap another another horizontal line segment, and vice versa for a vertical line segment, e.g. connecting $(9, 10)$ and $(8, 19)$ as shown below

Orthogonal connectors between row of equally spaced units

An acceptable connection between these units would look like this

Orthogonal connectors between row of equally spaced units

where the vertical line segments no longer overlap.

The only restriction is that each unit cannot 'support' more than one connection.


Here is the preferred solution to the special case of connectors between corresponding neighbouring upper and lower units e.g. $(0, 11)$ and $(1, 10)$

Orthogonal connectors between row of equally spaced units

$\endgroup$
11
  • $\begingroup$ What is the question? Are you simply looking for an arrangement of non-overlapping wires? $\endgroup$ Commented Jun 29, 2023 at 13:39
  • $\begingroup$ @InuyashaYagami Yes, that's what I am looking for. Please note that wires may cross each other but cannot lie on top of each other. $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 13:40
  • $\begingroup$ The connections are $(9,10)$ and $(8,19)$. I will upload what a proper layout for this case ought to look like. $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 13:52
  • $\begingroup$ Yes they can. Any upper unit can be connected to any lower unit in any permutation. The only restriction is that one unit cannot support more than one connection. $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 13:59
  • $\begingroup$ This is not always possible. Just think of $0\to11, 1\to10$. $\endgroup$
    – user16034
    Commented Jun 29, 2023 at 14:10

1 Answer 1

2
$\begingroup$

Let the upper row units be denoted by $u_1, \dotsc, u_N$ and lower row units be denoted by $\ell_1, \dotsc, \ell_N$. You can divide the region between the upper and lower rows into a grid $G$ of size $2N \times 2N$. For connecting $u_i$ to $\ell_j$ simply choose the path $G[1,2i]$ -> $G[2i,2i]$ -> $G[2i,2j-1]$ -> $G[2N,2j-1]$ (assuming $1$ based indexing).

Next, we show that for any two pairs $(u_i,\ell_j)$ and $(u_p,\ell_q)$ such that $i \neq p$ and $j \neq q$, the connections do not overlap.

Proof: Note that the horizontal line segment for connection between $u_i$ and $\ell_j$ uses row number $2i$ which is different from the row number $2p$, which is used by connection between $u_p$ and $\ell_q$ since $i \neq p$.

The vertical line segments uses the columns $2i$, $2j-1$, $2p$, and $2q-1$. Since an even numbered and odd numbered column can never overlap, we just need to check if $2i$ overlaps with $2p$ or $2j-1$ overlaps with $2q-1$. Since $i \neq p$ and $j \neq q$, overlapping is not possible.

$\endgroup$
5
  • 1
    $\begingroup$ I think I see what you did. The connectors start at even indexes (on the upper row) and end on odd indexes (on the lower row), and prevents overlapping of line segments by mandating them to travel on different indexes. This solution does satisfy the unspoken wishlist of (1) centring the connectors on the units or (2) allowing the two line segments to travel along the same index, where possible. The latter desirable would make this a search problem, wouldn't it? $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 16:05
  • $\begingroup$ @Olumide I did not understand this part: "The latter desirable would make this a search problem." $\endgroup$ Commented Jun 29, 2023 at 16:10
  • $\begingroup$ I meant to say that satisfying #2 of the unspoken wishlist would involve some sort of combinatorial search wouldn't it? BTW, what topic of CS does your solution belong to? $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 16:14
  • $\begingroup$ @Olumide Yeah. Maybe. Umm it is not a specific topic of CS. I guess computational geometry would be the closest. $\endgroup$ Commented Jun 29, 2023 at 16:28
  • $\begingroup$ Would you be open to a chatroom conversation? $\endgroup$
    – Olumide
    Commented Jun 29, 2023 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.