<p>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 <em>Computational Geometry in C</em>, <a href="https://books.google.com/books?id=gsv7HALW2jYC&amp;pg=PA272" rel="nofollow">pp. 272ff</a>. So the 3d problem can be solved in total time $O(n\log n)$.</p>

<p>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 <a href="https://books.google.com/books?id=vtkaCAAAQBAJ&amp;pg=PA28" rel="nofollow">Corollary 8(iii) of Agarwal and Erickson's range query survey</a>. 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$.</p>

CC BY-SA 3.0
2016-05-26T13:56:43.197Z
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
CC BY-SA 3.0
2016-05-26T18:11:55.890Z
@JosephStack "see Corollary 8(iii) of Agarwal and Erickson's range query survey"
David Eppstein
CC BY-SA 3.0
2016-06-01T08:42:11.423Z
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
CC BY-SA 3.0
2016-06-01T18:38:50.580Z
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
CC BY-SA 3.0
2016-04-26T22:44:58.600Z
2016-04-27T07:12:38.643Z
2016-04-27T07:12:38.643Z
David Eppstein
<p>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$).</p>

CC BY-SA 3.0
2016-04-26T09:27:03.913Z
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
CC BY-SA 3.0
2016-04-26T10:51:29.960Z
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
<ds.data-structures><time-complexity><computational-geometry><convex-hull>
maximizing inner product
Joseph Stack
# maximizing inner product

(Asked by: username_0 on 2016-04-26)

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

**Tags:** ds.data-structures, time-complexity, computational-geometry, convex-hull
> **Comments:**
> **username_0**: 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$.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2016-04-26. Score: 6 | Accepted answer

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](https://books.google.com/books?id=gsv7HALW2jYC&pg=PA272). 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](https://books.google.com/books?id=vtkaCAAAQBAJ&pg=PA28). 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$.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @JosephStack "see Corollary 8(iii) of Agarwal and Erickson's range query survey"  
> **username_0**: 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?  
> **username_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.  

---

