3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Naive solution is $O(n^2)$. Solution for $d=2$ is $\Theta(n\log n)$. A related question was posted on cstheory.stackexchange.com/questions/7719/…, 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$. $\endgroup$ – Joseph Stack Apr 26 '16 at 9:27
  • $\begingroup$ 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. $\endgroup$ – Joseph Stack Apr 26 '16 at 10:51
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joseph Stack May 26 '16 at 13:56
  • $\begingroup$ @JosephStack "see Corollary 8(iii) of Agarwal and Erickson's range query survey" $\endgroup$ – David Eppstein May 26 '16 at 18:11
  • $\begingroup$ 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? $\endgroup$ – Joseph Stack Jun 1 '16 at 8:42
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Jun 1 '16 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.