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$).
maximizing inner product
ds.data structures;time complexity;computational geometry;convex hull
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$.