2

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \langle p, p'\rangle$. I am only interested in $d=3$ (and possibly $d=4$).

Joseph Stack
  • 1,095
  • 6
  • 13
  • Naive solution is $O(n^2)$. Solution for $d=2$ is $\Theta(n\log n)$.
    A related question was posted on http://cstheory.stackexchange.com/questions/7719/a-data-structure-for-minimum-dot-product-queries, but the hardness result by R.Williams does not appear to apply as it exploits arbitrary large dimension. As discussed in the related question, we can safely normalize vectors from $L$.     – Joseph Stack Apr 26 '16 at 09:27
  • When $d=3$, vectors from $L$ are therefore determined by $2$ coordinates and we can assume $L'$ to be a convex hull. One of the comments suggests computing some Voronoi-like structure. Here I guess it would mean partitioning the plane into regions $V(p')$ such that $x,y\in V(p')$ iff $p'$ maximizes the product with $(x,y,\sqrt{1-x^2-y^2})$. However, the edges of this cell will not be straight lines, so it is not obvious how such a structure could be computed and used efficiently. – Joseph Stack Apr 26 '16 at 10:51

1 Answers1

6

For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is most extreme in the direction of $v$, and extreme-vertex queries may be answered in logarithmic time by using a Dobkin-Kirkpatrick hierarchy for the convex hull. For this part see e.g. O'Rourke's Computational Geometry in C, pp. 272ff. So the 3d problem can be solved in total time $O(n\log n)$.

For 4-dimensional vectors, the same thing would work, but you don't want to construct the convex hull because it's too expensive. Instead, it is possible to process a set of $n$ points in time and space $\tilde O(m)$ (for any $m$ between $n$ and $n^2$) so that you can answer extreme-point queries in time $\tilde O(n/\sqrt{m})$; see Corollary 8(iii) of Agarwal and Erickson's range query survey. Choosing $m=n^{4/3}$ gives total time $\tilde O(n^{4/3})$ to set up a data structure for $L'$ and query all vectors in $L$.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • A late question, but if I understand correctly, for $d=4$ your answer assumes there are algorithms for extreme point queries with $\langle\text{preprocessing, query}\rangle$ complexity $\langle n^2,\log n\rangle$ and $\langle n,\sqrt{n}\rangle$ respectively. Is it so, and would you have a pointer to these? – Joseph Stack May 26 '16 at 13:56
  • @JosephStack "see Corollary 8(iii) of Agarwal and Erickson's range query survey" – David Eppstein May 26 '16 at 18:11
  • This corollary only trades preprocessing for query once we know 2 algorithms satisfying certain conditions. But I am not aware of any algorithm for extreme point queries in dimension $>3$. Do you mean that halfspace reporting and extreme point queries are related? – Joseph Stack Jun 01 '16 at 08:42
  • 1
    Oh, that. Yes, if you can do halfspace emptiness testing (a special case of halfspace reporting) you can also find extreme points by applying parametric search to the queries. See e.g. Agarwal and Matousek, "Ray Shooting and Parametric Search", SICOMP 1993 (the dual problem). There is some overhead to the parametric search but it gets hidden in the $\tilde O$ notation. – David Eppstein Jun 01 '16 at 18:38