Centralizing four red vectors in six green sectors

Question

Four red vectors are given, one per quadrant, $[0,90^\circ)$, $[90^\circ,180^\circ)$, etc. A rigid star of six green vectors separated by $60^\circ$ can be positioned at $(\theta, \theta+60^\circ, \theta+120^\circ, \theta+180^\circ, \theta+240^\circ, \theta+300^\circ)$. The goal is to spin the green star so that the red vectors are centralized in green sectors as much as possible. Define the deviation $\delta(r)$ of a red vector $r$ as the larger of the (absolute value of the) two angles from the red vector to the boundaries of the green sector in which it lies. I want to minimize the largest red deviation.

For example, let the red vectors be at $(0^\circ, 90^\circ, 180^\circ, 270^\circ)$. Then choosing $\theta=15^\circ$ yields a deviation of $45^\circ$ for all red vectors. For example, $\delta(0^\circ) = \max \{ 15^\circ, 45^\circ \}$.

My question is: What is the largest deviation of any four red vectors? I thought it might approach $60^\circ$, but it seems that perhaps $52.5^\circ$ is the worst ($52.5^\circ = 7 \pi / 24$).

The problem generalizes to $k$ red vectors and $m > k$ green sectors. Likely the logic to establish the answer for $(k,m)=(4,6)$ will work for any $(k,m)$.

Answer 1

Replace each of your red vectors by its value modulo 60. You are then seeking to find a choice for $\theta$ that is as far as possible (mod 60) from any of the red vectors. The best choice for theta is to put it into the largest gap (mod 60) between red vectors, so the worst choice for the red vectors is for them to be equally spaced 15 degrees apart. With this choice, you get theta at distance 7.5 degrees from its nearest red vector or (as you already calculated) $\delta = 52.5 = 60 - 7.5$.

More generally, if you have k and m, the worst case is when the k vectors are equally spaced modulo $2\pi/m$, in which case the gaps between them have size $2\pi/km$, the distance from $\theta$ to the nearest red vector when it's placed in the middle of a gap will be $2\pi/2km$, and $\delta=\frac{2\pi}{m}-\frac{2\pi}{2km}=(1-\frac{1}{2k})\frac{2\pi}{m}$.

I don't understand why you want to restrict $m>k$ since the answer doesn't depend on that.

Answer 2

Assuming $k\le m$, the answer is $\frac{2\pi}{m}-\frac{\pi}{mk}$. I prefer to speak about red and green points on the circle rather than vectors. The angle between vectors is the (intrinsic) distance between points on the circle.

First, it does not matter that the red points are in different sectors: moving a red point the distance $\frac{2\pi}m$ along the circle does not change anything and point can be moved to any sector (this is where I use the assumption that $k\le m$). Second, it is easier to deal with the minimum distance between red and green, and maximize it (the answer is $2\pi/m$ minus the original one).

Fold the circle $m$ times along a circle of length $2\pi/m$. The red points are mapped to $k$ red points on the small circle, these are given. The green points are all mapped to one green point on the small circle, this one is variable. Now the goal is to place the green point as far as possible from the red ones. Obviously the best place is the midpoint of the longest arc between the red points, and the worst case is when the red points divide the small circle into equal arcs (of length $2\pi/mk$). Hence the answer is $\pi/mk$.