3
$\begingroup$

Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements in each interval.

Therefore it´s necessary to merge the intervals of the first type and the intervals of the second type separately. It is important to know that the intervals of a tuple have a relationship. Thus, a tuple cannot be merged with another tuple unless both intervals can each be merged separately with the interval belonging to them.


An example:

Let valid values for the first elements of the tuples are number intervals. Let valid values for the second elements of the tuples are character intervals.

A valid optimization of [{[1-3], [a-d]}, {[4-7],[e-f]}] would be [{[1-7], [a-f]}. But it is not possible to simplify tuples like [{[1-3], [a-d]}, {[7-9], [e-k]}] because between 1-3 and 7-9 there are still the numbers {4, 5, 6}.


I am looking for efficient algorithms to simplify this kind of list of tuples that contains intervals.

A simple solution would be to simply check all combinations. But how can large datasets be optimized? Checking all combinations would cost to many ressources.

So my questions are:

  • Are there well-known (efficient) algorithms for such tasks, such as approximation algorithms? I'm looking for a kind of merge intervals algorithm, but for tupels. It should optimize both attributes so that one gets fewer elements in the tuples list.
  • Is this a well-known problem? (Is there a reduction from some NP-complete problem?) I guess my problem is somehow related to the set cover problem? Am I right?

Thanks for any help!

$\endgroup$
6
  • $\begingroup$ Can intervals be merged only if they do not intersect? What is the measure you are trying to optimize? $\endgroup$
    – Steven
    Jul 14, 2021 at 9:35
  • 1
    $\begingroup$ Construct an undirected graph $G = (V,E)$, where vertices represent tuples and an edge $(u,v)$ means tuple $u$ and tuple $v$ can be merged. Now, simply find the number of connected components in the graph. That would be the answer. $\endgroup$ Jul 14, 2021 at 13:45
  • 2
    $\begingroup$ @InuyashaYagami. Unfortunately that doesn't work. Consider the pairs of intervals $p_1 = ( [3-3], [b-b] )$, $p_2 = ( [2-2], [c-c] )$, $p_3 = ([1-1], [a-a])$. A valid sequence of merges consists of merging $p_1$ with $p_2$ and then the resulting interval $([2-3], [b-c])$ with $p_3$ yielding $([1-3], [a-c])$. However $p_3$ cannot be merged with neither $p_1$ (because of the first interval) nor with $p_2$ (because of the second interval). Therefore $p_3$ would be an isolated vertex in $G$. $\endgroup$
    – Steven
    Jul 14, 2021 at 14:36
  • 1
    $\begingroup$ @Steven I think the algorithm from InuyashaYagami works if the algorithm is extended. If after each merge the graph is recalculated for the resulting tuple, it should work. However, this would then entail costs for the recalculation for each merge. $\endgroup$
    – df21
    Jul 14, 2021 at 14:56
  • 2
    $\begingroup$ Then the algorithm is just the greedy algorithm that iteratively finds any two pairs that can be merged and merges them. $\endgroup$
    – Steven
    Jul 14, 2021 at 15:12

1 Answer 1

2
$\begingroup$

Consider the greedy algorithm that iteratively searches for two distinct pairs of intervals that can be merged, merges them, and repeats until no more merges are possible.

We need to show that this algorithm is optimal. Notice that, at each point in time during the algorithm, we can associate the generic $i$-th pair $\mathcal{I}_i$ with a set $P_i$ containing all the original pairs that were ultimately merged into $\mathcal{I}_i$.

Similarly, consider an optimal solution $\mathcal{I}^*_1, \mathcal{I}^*_2, \dots, \mathcal{I}^*_\ell$ and define $P^*_1, \dots, P^*_\ell$ as the corresponding sets of original pairs. Let $k$ be the number of intervals returned by the greedy algorithm. We want to show that $k \le \ell$ (which implies $k = \ell$).

We start by showing that the final sets induced by an execution of the greedy algorithm must be a refinement of $P^*_1, \dots, P^*_\ell$. Suppose that this is false and pick the first point in time at which the greedy algorithm merges two pairs $\mathcal{I}_i$ and $\mathcal{I}_j$ associated with sets $P_i$ and $P_j$ where $P_i \subseteq P^*_h$ and $P_j \subseteq P^*_z$ with $h \neq z$. Since $\mathcal{I}_i$ can be merged with $\mathcal{I}_j$, $\mathcal{I}^*_h$ contains $\mathcal{I}_i$, and $\mathcal{I}^*_z$ contains $I_j$, we must have that $\mathcal{I}^*_h$ can be merged with $\mathcal{I}^*_z$ contradicting the optimality of $\mathcal{I}^*_1, \mathcal{I}^*_2, \dots, \mathcal{I}^*_\ell$.

Suppose now that $k > \ell$. Then there is some set $P^*_h$ that is partitioned into $m \ge 2$ sets $P'_{1}, \dots, P'_{m}$ from $\{P_1, \dots, P_k\}$. Let $\mathcal{I}'_i$ be the pair corresponding to $P'_i$. The merge operation that resulted in $P^*_h$ can be described as a binary tree $T$ in which each leaf represents a pair in $P^*_h$, every internal node $v$ represents a merged pair $\mathcal{I}(v)$, and the root $r$ represents $\mathcal{I}(r) = \mathcal{I}^*_h$. Let $P(v)$ be the set corresponding to $\mathcal{I}(v)$. Locate the deepest vertex $v$ in $T$ such that its two children $u$ and $w$ satisfy $P(u) \subseteq P'_i$ and $P(w) \subseteq P'_j$ for $i \neq j$. We must have that $\mathcal{I}'_i$ contains $\mathcal{I}(u)$ and $\mathcal{I}'_j$ contains $\mathcal{I}(w)$. Therefore, since $\mathcal{I}(u)$ and $\mathcal{I}(w)$ can be merged into $\mathcal{I}(v)$, the pairs $\mathcal{I}'_i$ and $\mathcal{I}'_j$ can also be merged. This contradicts the stopping condition of our greedy algorithm.

To implement the greedy algorithm efficiently you can first transform the input instance so that two pairs can be merged if and only if their intervals intersect. Then interpret the intervals in a pair as the sides of a rectangle.

Use a data structure $D$ that is able to (i) maintain a dynamic collection of rectangles and (ii) report all rectangles intersecting with a given query rectangle. For example, you can use a dynamic range tree that supports each of the above operations in $O(\mathrm{polylog}\, m)$ amortized time, where $m$ is the number of stored rectangles.

Repeat the following:

  • For each input pair $\mathcal{I}$:
    • While $D$ contains some pairs (rectangles) that intersect with $\mathcal{I}$.
      • Delete all such pairs from $D$ and let $\mathcal{I}$ be the pair obtained by merging $\mathcal{I}$ with all of them.
    • Insert $\mathcal{I}$ into $D$.

At the end of the algorithm, the contents of $D$ are exactly the final set of pairs. To analyze the time complexity of this algorithm notice that each original pair is inserted at most once into $D$ and can be associated to exactly one query to $D$ that does not satisfy the condition of the while loop. Moreover, the number of merged pairs is at most $n-1$, where $n$ is the number of pairs in input. Each merge inserts at most one pair into $D$ and is respondible for one query. The number of pairs deleted from $D$ is upper bounded by the number of insertions. Overall we perform $O(n)$ operations on $D$.

The overall time needed is then $O(n \, \mathrm{polylog} \, n)$.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your useful answer! $\endgroup$
    – df21
    Jul 14, 2021 at 20:44
  • 1
    $\begingroup$ I'm glad it helped! $\endgroup$
    – Steven
    Jul 14, 2021 at 20:52

Your Answer

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

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