# find separate pairs of points with minimal total distance

I am looking for suitable algorithm how to solve the following problem.

For finite set $$S \subset \mathbb{R}$$ ($$|S| = N_{S}$$) we need to find its disjunctive separation $$S = A \cup B$$ ($$A \cap B = \emptyset$$) on two ordered sets and assignment $$\pi$$ between elements of these two sets, where the following conditions must be fulfilled:

1. $$|A| = |B| = N$$ where $$N = \lfloor N_s/2 \rfloor$$
2. $$s_k \in S$$ where $$k = 1,2, ...,N_s$$
3. $$a_i \in A$$ and $$b_j \in B$$ where $$i,j = 1,2, ..., N$$
4. $$\sum_{i=1}^{N}|a_{\pi(i)} - b_i| \to min$$

In other words, I am looking for method how to find set of separated pairs $$[a_{\pi(i)},b_i]$$ assignments.

Example: $$S = [3.0, 2.1, 0.9, 2.9, 1.1], N_s = 5, N = 2$$ then $$A = [3.0, 0.9]$$ and $$B = [2.9, 1.1]$$ which produce following separate pairs:

$$[3.0, 2.9], [0.9, 1.1]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.

## 1 Answer

Sort the items so that $$s_1 \le s_2 \le \dots \le s_{N_S}$$. Then:

• If $$N_S$$ is even, assign all the odd-numbered items to $$A$$, all even-numbered items to $$B$$, and pair the first item of $$A$$ with the first of $$B$$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more.

• If $$N_S$$ is odd, enumerate over all possible items $$s_i$$ in $$S$$ and for each of them, compute the best partition of $$S \setminus \{s_i\}$$, which is an even-size set, using the previous case. Return the best partition among all $$N_S$$ cases.

The total cost of this procedure is $$O(N_S \log N_S)$$ when $$N_S$$ is even and $$O(N_S^2 \log N_S)$$ when $$N_S$$ is odd.

• Nice! You can speed up the case of odd $N_S$ to run in $O(N_S \log N_S)$ time by a "prefix/suffix sum" type of trick: when $i$ is even, let $t_i$ denote the cost of the best partition of $s_1,\dots,s_i$; when $N_S-i+1$ is even, let $u_i$ denote the cost of the best partition of $s_i,\dots,s_{N_S}$. After sorting the $s_i$'s, you can compute the $t_i,u_i$'s in $O(N_S)$ time. Then you can compute the cost of the best partition of $S \setminus \{s_i\}$ in $O(1)$ time per $s_i$ from $t_{i-1}$ (or $t_{i-2}$) and $u_{i+1}$ (or $u_{i+2}$). – D.W. Mar 29 '19 at 15:13
• @D.W. Great! Could you provide simple pseudo code realization of prefix/suffix sum approach regarding this specific problem? I am not sure if I understand well your brief description. – michalkvasnicka Mar 29 '19 at 15:27
• OK. Define $t_{2j} = t_{2j-2} + |s_{2j} - s_{2j-1}|$ and $u_{2j} = u_{2j+2} + |s_{2j+1} - s_{2j}|$. If $i$ is odd, the cost of the best partition of $S \setminus \{s_i\}$ is $t_{i-1} + u_{i+1}$. If $i$ is even, the cost of the best partition of $S \setminus \{s_i\}$ is $t_{i-2} + u_{i+2} + |s_{i+1}-s_{i-1}|$. You can compute all the $t$'s and $u$'s in linear time, then compute all of the costs of the best partition of $S \setminus \{s_i\}$ for all $i$ in linear time, then pick the one of lowest cost. @michalkvasnicka – D.W. Mar 29 '19 at 16:35
• @D.W. Sorry, but I still do not understand your indexing. Could you show me how looks like vectors $t_i$ and $u_i$, for $i=1,2,, ...,N_S$ in my simple example? – michalkvasnicka Apr 1 '19 at 10:57
• @D.W. Your indexing is a bit confusing. For $i=1$ you have element $t_{i-2} = t_{-1}$. How is defined this element, for example? – michalkvasnicka Apr 1 '19 at 12:08