Let $G$ be a finite group acting linearly on $\mathbb{R}^N$. For $x,y \in \mathbb{R}^N$, when is there a fast algorithm, $\mathcal{O}((\log|G|)^k)$ for some $k$, to compute $\displaystyle \max_{g \in G} x \cdot \sigma y$? This is equivalent to computing a representative in a Dirichlet fundamental domain centered at $x$, or $\displaystyle d_{\mathbb{R}^N/G}(x,y)=\min_{g \in G}d(x,gy)$.
When $G=\langle \omega \rangle$ is a cyclic group of order $n$ acting on $\mathbb{R}^2$ by rotations, one can use $\mathcal{O}(\log_2(n))$ elements $\omega^{\pm \lfloor n/2^i \rfloor}$, and for each pair see if one or the other increases $x\cdot gy$, performing a circular "binary search".
When $G=G_1 \times \ldots \times G_k$ is a product acting "diagonally" on $\mathbb{R}^N=\mathbb{R}^{r_1} \times \ldots \times \mathbb{R}^{r_k}$, with $g_i^*$ maximizing the $i^{th}$ factor, $g^*=(g_1,\ldots,g_k)$.
When $G=\Sigma_N$ is the permutation group on $N$ symbols, this is finding a permutation which orders $y$ with respect to the order of $x$, which is $\mathcal{O}(N\log(N))$.
I'm most interested in the case $G=\Sigma_n \hookrightarrow \Sigma_N$, where $N=\binom{n}{2}$, with $\Sigma_n$ acting on $N$ unordered pairs via $\sigma\{i,j\}=\{\sigma(i),\sigma(j)\}$ for $1 \le i < j \le n$. I'm thinking of $\mathbb{R}^N$ as the space of weighted networks, and $\Sigma_n$ is relabeling the vertices, inducing edge relabelings.
This case is at least as hard as graph isomorphism, since we can take edge weights to be in $\{0,1\}$, and two graphs are isomorphic iff $\exists \sigma \in \Sigma_n$ such that $x = \sigma y$.
I imagine this problem is intractable for most $G$, but mostly I'm just curious if this problem has a name, and if there are any interesting cases where it has been solved. For $\Sigma_n \subset H \subset \Sigma_N$, it seems that the complexity must increase as $H$ gets smaller.