2
$\begingroup$

Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define $$ S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \} $$ and $$ f(s) = \min_{t,z_1,z_2,x,y} \{ t : (s, t, z_1, z_2, x, y) \in S \} $$ with $f(s) = \infty$ if the feasible set of the above minimum is empty. I would like an efficient algorithm for computing the set $$ R = \{ (s, f(s), z_1, z_2) : (s,f(s),z_1,z_2,x,y) \in S \text{ for some $x$,$y$ } \} $$

Of course, a naive $\mathcal{O}(mn ~\log(mn))$ with $m=|A|,~n=|B|$ method follows directly from the definition. Embed the set $S$ to an array of tuples, group by equal values of $z_1+z_2$ by sorting, and within each group choose the element with minimum $x+y$. I am wondering weather a better method is known.

Update

There are two additioal assumption which I believe can lead to a better algorithm.

  • There is a finite family $F \subseteq \mathbb{C}$ such that if $(z, x) \in A \cup B$ then $z \in F$. The family $F$ is a grid (or lattice?) in the complex plane, with uniform spacing in each direction. However, the spacing in the real direction can be different from the spacing in the imaginary direction.
  • Both $|A|$ and $|B|$ are in $\mathcal{O}(|F|)$.

Output-size sensitive complexity bound, which could somehow reduce the dependence on $mn$ would be a tremendous improvement, since the size of the output seems to me as $O(m+n)$.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ $|R|$ can be as large as $\Omega(mn)$, so I guess not much improvement can be done? $\endgroup$ – Willard Zhan Oct 17 '17 at 15:35
  • $\begingroup$ $f(s)$ is just the global minimum of $x+y$, so you don't need to do any sorting. Just find the pair with smallest second component (say, $a$) in $A$ (in $O(m)$ time), and the pair with the smallest second component (say, $b$) in $B$ (in $O(n)$ time) and add those second components to determine $f(s)$. The only elements in $R$ with $f(s)$ for their second components are those produced from some $(\cdot, a) \in A$ and some $(\cdot, b) \in B$ (why?), so use a second pass through each set to collect all of these, and then output all pairs. $\endgroup$ – j_random_hacker Oct 17 '17 at 17:55
  • $\begingroup$ @j_random_hacker, $f(s)$ is the global minimum of $x+y$ which corresponds to that specific $s$. For any $s$ it has a different value. Thus, I currently do not see any way to avoid grouping by equal values of $s=z_1+z_2$. $\endgroup$ – Alex Shtof Oct 18 '17 at 7:11
  • $\begingroup$ @WillardZhan, after some analysis I have more assumptions to add, which might allow for a more efficient solution. I will write an update. $\endgroup$ – Alex Shtof Oct 18 '17 at 7:12
  • $\begingroup$ Sounds like you want a convolution over the tropical smearing $(+,\min)$ instead of the usual ring $(\times,+)$. I don't know whether there is some equivalent of the FFT known for this semigroup? That might be called max-convolution. Maybe relevant: drops.dagstuhl.de/opus/volltexte/2017/7421/pdf/… $\endgroup$ – D.W.♦ Oct 18 '17 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.