For two non-empty finite sets $A,B$ in the real line define the $\ell\_1$-distance $d\_1(A,B)$ between $A$ and $B$ as the smallest Lebesgue measure of a closed subset $\Gamma\subset \mathbb R$ such that $A\cup B\subset\Gamma$ and each connected component of $\Gamma$ intersects both sets $A$ and $B$. It is clear that such minimal set $\Gamma$ is a disjoint union of closed intervals with ends in the set $A\cup B$. As was noted by @fedja in his comment, the number of such unions is $\le 2^{n-1}$ where $n$ is the cardinality of the set $A\cup B$.


So, a brute force algorithm for calculating the distance $d\_1(A,B)$ has exponential complexity.


**Problem.** Is there a polynomial-time algorithm for calculating $d\_1(A,B)$? Or this problem is NP-hard? NP-complete?


**Remark.** A similar problem for the plane seems to be NP-hard, see Remark 2 [here](https://mathoverflow.net/questions/277604/a-new-ell-p-metric-on-the-hyperspace-of-finite-sets).



A quick algorithm for calculating the $\ell_1$-distance between two finite sets on the real line?
While it doesn’t seem to be possible to beat the $O(n\log n)$ bound for general input, the problem can be solved in time $O(n)$ if $A\cup B$ is given sorted.


This builds on the ideas in fedja’s and Aaron Meyerowitz’s answers. As implicit in the other posts, I am assuming unit-cost real RAM or a similar model, so that arithmetic operations on real numbers are exact and take constant time.


Let $A\cup B=\{x\_1,\dots,x\_n\}$ with $x\_1<x\_2<\dots<x\_n$. In order to compute $d\_1(A,B)$, we will compute the sequence of numbers
$$\begin{align\*}
u\_i&=d\_1\bigl(A\cap[x\_1,x\_i],B\cap[x\_1,x\_i]\bigr),\\
v\_i&=d\_1\bigl((A\cup\{x\_i\})\cap[x\_1,x\_i],(B\cup\{x\_i\})\cap[x\_1,x\_i]\bigr)
\end{align\*}$$
for $i=1,\dots,n$. This can be done in linear time using the following recurrence:
$$\begin{align\*}
v\_1&=0,\\
u\_1&=\begin{cases}0&x\_1\in A\cap B,\\\infty&\text{otherwise,}\end{cases}\\
v\_{i+1}&=\min\bigl\{u\_i,v\_i+(x\_{i+1}-x\_i)\bigr\},\\
u\_{i+1}&=\begin{cases}
 v\_{i+1}&x\_{i+1}\in A\cap B,\\
 v\_i+(x\_{i+1}-x\_i)&x\_{i+1}\in A\smallsetminus B\text{ and }x\_i\in B,\text{ or v.v.,}\\
 u\_i+(x\_{i+1}-x\_i)&x\_{i+1},x\_i\in A\smallsetminus B,\text{ or v.v.}
\end{cases}
\end{align\*}$$
(Some optimization is possible, treating blocks of elements belonging to the same set in bulk. However, this does not improve the worst-case asymptotic complexity.) Note that the two cases in the minimum in the computation of $v\_{i+1}$ correspond to the choice whether $[x\_i,x\_{i+1}]$ is in $\Gamma$ or not. It is straightforward to extend the algorithm so that it also outputs a witnessing sequence of intervals.


Hausdorff distance can be also computed in time $O(n)$ on sorted input, using the following pseudocode:



```
/* for each i, find distance to the maximal y \le x_i that belongs to the other set: */
lastA := lastB := -\infty
for i := 1 to n do:
  if x_i in A then lastA := x_i
  if x_i in B then lastB := x_i
  if x_i in A then d_i := x_i - lastB
              else d_i := x_i - lastA
/* do the same thing backwards, and compute the result along the way */
lastA := lastB := \infty
d := 0
for i := n downto 1 do:
  if x_i in A then lastA := x_i
  if x_i in B then lastB := x_i
  if x_i in A then d_i := min (d_i, lastB - x_i)
              else d_i := min (d_i, lastA - x_i)
  d := max (d, d_i)
return d

```

