Skip to main content
MathOverflow

Return to Answer

Removed unclosed parenthesis
Source Link
Michael Albert
Michael Albert
  • 1.3k
  • 6
  • 11

I am going to try to answer the version of the Observation (whichwhich seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.

I am going to try to answer the version of the Observation (which seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.

I am going to try to answer the version of the Observation which seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.

Source Link
Michael Albert
Michael Albert
  • 1.3k
  • 6
  • 11

I am going to try to answer the version of the Observation (which seems to imply that the original "orthogonal" basis condition really is meant to mean "positive multiples of the standard basis vectors". So the problem is, given positive real numbers $x_1$, $x_2$, ..., $x_j$, produce the first $M$ elements of the set $x_1 \mathbb{N} + x_2 \mathbb{N} + \cdots + x_j \mathbb{N}$ in order. For simplicity I'm going to ignore the possibility of ties (this is easily dealt with). The basic idea is just to think of this as a shortest paths problem in the graph $\mathbb{N}^j$ (where the edges are given by the standard basis vectors $e_i$ and the weight of the edge $e_i$ is $n_i$.) Now Dijkstra's algorithm does this efficiently (we can just stop when the $M$ nearest neighbours are found). For this particular set up there are even some extra gains to be made -- since we know that the distance to a vertex is independent of the path used to get to it, we can choose a standard path to every vertex (e.g., go along the first dimension, then the second, ...) and only add those neighbours that extend such standard paths.