What is the complexity of comparing point sequences?

Question

Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point pattern $X$ into a pattern $Y$ by deleting, adding, and moving points (that is adding a constant to all points). The cost of a transformation is:

$$p_d|X_{delete}| + p_a|X_{add}| + p_m d$$

where $p_a$, $p_d$ and $p_m$ are parameters and $X_{delete}$ and $X_{add}$ are subsets of $X$ that are deleted and added. $|X_{delete}|$, for example, is the number of elements in $|X_{delete}|$ and not the sum of the values. $d$ is the value that we are adding to all the points in the sequence $X$.

For example, say $X = (1,2,3)$ and $Y = (2,4)$ then one possible transformation of $X$ into $Y$ has cost $p_d + p_m$ as we can delete $2$ from $X$ and then increase both the points in $X$ by $1$ to make $(2,4)$ (so $d = 1$).

By adding a point I mean inserting a new point into the array.

I am trying to work out what the complexity of computing this distance is. It is not obvious to me how to do this by dynamic programming for example.

---

@Gassa gives a solution using $O(n^2)$ hash function calls. Is there a simple dynamic programming (or other) solution that doesn't require any hash function calls at all?

Answer 1

Here's a start: an upper bound is $O(n^3)$.

Note that we need either $0$ or $1$ moves: any two moves could be expressed as one. Furthermore, this one move is commutative with all other operations: it may occur at any point in time, the end result will still be the same.

Barring some degenerate cases, consider one point $X_i$ which does not get deleted and moves into $Y_j$. There are a total of $n^2$ such possibilities. For each fixed $i$ and $j$, first, we know whether we need a move, and second, for all other points, we can establish which $X_u$ move into which $Y_v$ in $O(n)$. For example, put all $Y_v$ in a hash table in $O(n)$, iterate over all $X_u$ and search for them in the hash table in $O(n)$ total.

---

Here's a speedup to $O(n^2)$.

Consider all possible $n^2$ move distances: each "$X_i$ to $Y_j$" produces a distance. Some of the distances may turn out to be the same. In your example of $X = (1, 2, 3)$ and $Y = (2, 4)$, the $X_1 \to Y_1$ and $X_3 \to Y_2$ produce the same distance of $2$. So, in the end, each distance will have several pairs associated with it.

Now, we will need all $X_i$ to be different, and all $Y_j$ to be different. Then, if a distance $d$ has $r$ pairs associated with it, all $X_i$ in these pairs are pairwise different, and all $Y_j$ in these pairs are also pairwise different. It means that, when we move points by distance $d$, we will have $r$ matching points, and all other points will be non-matching, so will have to be deleted from $\{X\}$ or inserted into $\{Y\}$, respectively.

So, implementation-wise, maintain a hash map which maps a distance to the number of times we encountered such distance. Iterate over all pairs of "$X_i$ to $Y_j$" and fill the map, in $O(n^2)$ total. Now iterate the map and find the minimum cost, also in $O(n^2)$ total. For a distance $d$, when the number of pairs with such distance is $r (d)$, the cost is the sum of the following:

• $p_m$ if $d$ is nonzero, or $0$ if $d$ is zero;
• $p_d \cdot (l_X - r (d))$, where $l_X$ is the length of $\{X\}$;
• $p_a \cdot (l_Y - r (d))$, where $l_Y$ is the length of $\{Y\}$.

It may be possible to handle the case when the sequences can contain equal elements, but the details look cumbersome.

---

All this assumes $O(1)$ performance of hash sets and hash maps. If that is a problem, at the very least, we can add logarithms and use tree sets and tree maps, respectively.

Also, the solution does not address precision loss for floating point operations. For example, the implementation may use integers, by multiplying the given floating point values values by a constant.