# Orthogonal connectors with non-overlapping horizontal or vertical line segments

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,

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

An acceptable connection between these units would look like this

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)$$

• What is the question? Are you simply looking for an arrangement of non-overlapping wires? Commented Jun 29, 2023 at 13:39
• @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. Commented Jun 29, 2023 at 13:40
• The connections are $(9,10)$ and $(8,19)$. I will upload what a proper layout for this case ought to look like. Commented Jun 29, 2023 at 13:52
• 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. Commented Jun 29, 2023 at 13:59
• This is not always possible. Just think of $0\to11, 1\to10$.
– user16034
Commented Jun 29, 2023 at 14:10

## 1 Answer

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.

• 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? Commented Jun 29, 2023 at 16:05
• @Olumide I did not understand this part: "The latter desirable would make this a search problem." Commented Jun 29, 2023 at 16:10
• 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? Commented Jun 29, 2023 at 16:14
• @Olumide Yeah. Maybe. Umm it is not a specific topic of CS. I guess computational geometry would be the closest. Commented Jun 29, 2023 at 16:28
• Would you be open to a chatroom conversation? Commented Jun 29, 2023 at 16:38