Skip to main content
2 of 6
added 5 characters in body
flawr
  • 43.9k
  • 41
  • 41

#plan an efficient finnish bus stop on a sphere

Apparently respecting personal space is very important at finnish bus stops. Now given some "minimum-personal-space-angle" \$\vartheta\$, your job is designing a bus stop on a sphere for as many people as possible respecting the "minimum-personal-space-angle".

Let us rephrase this a little bit more clearly: Let \$S^2 = \{x \in \mathbb R^3 \mid \Vert x \Vert_2^2 =1 \}\$ be the unit sphere in \$\mathbb R^3\$. Given the angle \$\vartheta \in (0,\pi)\$ you should find a set \$U \subset S^2\$ such that all pairs of vectors \$x,y \in U\$ (\$x \neq y\$) are at least an angle of \$\vartheta\$ apart, that is \$x \cdot y \leqslant \cos \vartheta\$.

And this set \$U\$ should be as large as possible - but this does not mean that your program needs to find the largest possible \$U\$ (this is a hard unsolved problem), but it should try to make it as large as possible as this will be part of the score.

Let us define \$a_\theta = \vert U \vert\$ as the number of vectors your program found for \$\theta\$.

The score \$s\$ of your submission will be

$$ s=\frac{1}{N}\sum_{n=1}^N a_{\theta_n} w_n$$

where \$\theta_n = 1/n\$, \$w_n = 1/n^2\$. And you can choose \$N \in \mathbb N\$ as large as you want.

Inspired by this reddit thread.

#META: I think the choice of \$\theta_n\$ and \$w_n\$ needs some fine tuning to make the challenge interesting. My thoughts so far: The idea is that \$a_{\theta} \leqslant c \frac{1}{\theta^2}\$ since every vector on the sphere needs a circle of a radius that is at least \$\theta/2\$, so the area of such a circle is about \$\pi (\theta/2)^2\$ which means we can fit at most \$\frac{4\pi}{\pi (\theta/2)^2} = \frac{1}{\theta^2}\$ (just as a rough estimate).

So I think with current choice of \$\theta_n\$ and \$w_n\$ the score should be bounded. But I fear that with the current choice of these sequences the greatest score will be achieved by a relatively simple solution where someone just chooses \$N=1,2\$ or so.

Can we alleviate this by adding a factor of \$\log n\$ to \$w_n\$? Unfortunately I think this would incentivise using very large \$N\$.

If you have any thoughts or ideas, please share!

flawr
  • 43.9k
  • 41
  • 41