# Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason.

Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.

I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace 0,\ldots,n-1\rbrace \times \lbrace 0,\ldots,n-1\rbrace$ so as to maximize the sum, over all $p$ in $S$, of the dot product $p \cdot f(p)$.

If, instead of $\mathbb{R}^2$, I had $\mathbb{R}^1$, and I was putting $S$ in bijection with $\lbrace0,\ldots,n-1\rbrace$, then this would simply be sorting $S$ and one knows how to do that fast.

For this problem, it's not even obvious to me how to do it in a number of steps that's polynomial in $n$.

Is this easy? Is it an example of a known genre of optimization problem?

-
I am somewhat tempted to vandalize your title by inserting a colon after the word "weirdo"... Nice question, by the way – Yemon Choi Nov 4 '11 at 2:42
It would help to be more explicit about the goal. Please clarify p . f(p)? Gerhard "Ask Me About System Design" Paseman, 2011.11.03 – Gerhard Paseman Nov 4 '11 at 2:54
It's a dot product, with the lattice points viewed as elements of the inner product space $\mathbb R^n$. Note to asker: mathbb is the command to make your R's look cool. Your problem is certainly a linear programming problem. I don't know anything more specific. – Will Sawin Nov 4 '11 at 3:10
Well, en.wikipedia.org/wiki/Hungarian_algorithm certainly works here but, perhaps, you can do even better. – fedja Nov 4 '11 at 3:14

To elaborate on the comments of Will Sawin and fedja: The question isn't a sorting problem, but it is a matching problem. If $S$ is your arbitrary set and $G = [n]^2$ is your grid, then you are marrying elements of $S$ to elements in $G$, where the happiness of each marriage is your dot product $p \cdot f(p)$. Any happiness function on $S \times G$, not necessarily one that is bilinear in the plane, can be maximized in polynomial time. That's because the convex hull of the set of permutation matrices has few facets: It's the Birkhoff polytope of doubly stochastic matrices. You can apply the general theorem that linear programming with polynomially many facets can be done in polynomial time. For the specific case of the Birkhoff polytope, there is an optimized linear programming algorithm, the Hungarian algorithm, that was discovered and known to be fast before the result that LP is polynomial time in general.