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)$.