[Math] Optimal Resolvable Steiner Quintuple System covering with circles and ellipses

combinatoricsoptimization

Here is a resolvable Steiner quintuple system. Every tuple from 1-25 appears in exactly one of the sets.
{{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25},
{1,6,11,16,21},{2,7,12,17,22},{3,8,13,18,23},{4,9,14,19,24},{5,10,15,20,25},
{1,7,13,19,25},{2,8,14,20,21},{3,9,15,16,22},{4,10,11,17,23},{5,6,12,18,24},
{1,10,14,18,22},{2,6,15,19,23},{3,7,11,20,24},{4,8,12,16,25},{5,9,13,17,21},
{4,6,13,20,22},{25,2,9,11,18},{16,23,5,7,14},{12,19,21,3,10},{8,15,17,24,1},
{4,18,7,21,15},{6,25,14,3,17},{13,2,16,10,24},{20,9,23,12,1},{22,11,5,19,8}}

It's possible to cover this as a point system with ellipses and circles. An optimal covering would be one where each ellipse and circle clearly went through exactly 5 points, and didn't come close to any others. Is there a good way to optimize this?

ellipse covering of Steiner system

Best Answer

This incidence structure is not a Steiner quintuple system (they can only exist when $v=3,5\pmod{6}$). What you have is a $2$-design, and in particular a $(25,5,1)$-BIBD.

Related Solutions

Finding optimal way to steer a system to origin with input constraints

You also have to take the absolute value of $u(t)$ into account. Namely say $\lambda_2=0.5$ then your solution gives $u(t)=-1$ with $|u(t)|+u(t)\,\lambda_2=0.5$. However, $u(t)=0$ yields $|u(t)|+u(t)\,\lambda_2=0$ which is lower. Namely $|u(t)|$ is the dominant term when $|\lambda_2|<1$, which has the minimum $u(t)=0$. So the expression which would minimize the Hamiltonian would be

$$ u(t) = \left\{ \begin{array}{ll} 1, & \text{if}\ \lambda_2 < -1 \\ -1, & \text{if}\ \lambda_2 > 1 \\ 0, & \text{otherwise} \end{array} \right. . $$

You still need to find values for $\lambda_1(0)$ and $\lambda_2(0)$, however I am not sure there would be a closed form solution for it. There isn't even always a solution, for example if $t_f$ is too small such that the constrained input can't drive the system from its initial conditions to zero. In general this is solved with the shooting method. In the case that $(x(t_f),\dot{x}(t_f))=(0,0)$ then $(\lambda_1(t_f),\lambda_2(t_f))$ is allowed to be anything. In the case that only $x(t_f)=0$ ($\dot{x}(t_f)$ can be anything) then $\lambda_1(t_f)$ can still be anything, however the other co-state has to satisfy

$$ \lambda_2(t_f) = \left[\frac{\partial g_{t_f}}{\partial \dot{x}}\right]_{x=x(t_t)}, $$

with $g_{t_f}$ the terminal cost, which in this case is zero.

Covering each point of the plane with circles three times

Below I construct a cover of $\mathbb{R}^2$ with degree $3$. The idea is to build an almost-"degree 2 cover" of $\mathbb{R}^2$ for which a single point is covered three times (using variations on the trick from the degree 2 cover given in the question), then to balance things out by adding the degree $1$ cover of $\mathbb{R}^2 - \{O\}$.

Lemma: Let $U$ be an open disk and let $P$ be a point on its boundary. Then there is a family $\mathscr{F}$ of circles contained in $U \cup \{P\}$ such that each point of $U$ belongs to exactly two circles of $\mathscr{F}$, while $P$ belongs to exactly one circle of $\mathscr{F}$.

Proof: For $a > 0$, let $L(a)$ be the line given by the equation $x = a$, and let $C(a)$ be the circle of radius $a$ centered at $(a, 0)$, so $C(a)$ passes through the origin $O$. Assume without loss of generality that $P = O$ and that $U$ is the open disk bounded by $C(1/2)$. Now, for $0 < a < b$, let $\mathscr{G}(a, b)$ be the family of circles of radius $\frac{b-a}{2}$ with centers on the line $L(\frac{b+a}{2})$, so the circles of $\mathscr{G}(a, b)$ are contained within the closed strip bounded by $L(a)$ and $L(b)$, and each point of $L(a)$ and $L(b)$ belongs to exactly one circle of $\mathscr{G}(a, b)$, while each point in the interior of the strip belongs to exactly two circles of $\mathscr{G}(a, b)$. Define $$\mathscr{G} = \bigcup_{n=1}^\infty \mathscr{G}\left(1 + \frac{1}{n+1}, 1 + \frac{1}{n} \right) \cup \bigcup_{n=1}^\infty \mathscr{G}\left(2 + \frac{1}{n+1}, 2 + \frac{1}{n} \right) \cup \bigcup_{n=3}^\infty \mathscr{G}(n, n+1)$$ so that, if we define $V = \bigcup_{a > 1} L(a) = \{(x, y) : x > 1\}$, all circles in $\mathscr{G}$ are contained in $V$, and each point in $V$ belongs to exactly two circles in $\mathscr{G}$, except for those points in $L(2)$, each of which belongs to exactly one circle in $\mathscr{G}$. Now, under inversion with respect to the unit circle centered at the origin, $L(a)$ maps to $C(\frac{1}{2a}) - \{O\}$, $V$ maps to $U$, and each circle in $\mathscr{G}$ maps to a circle in a new family $\mathscr{G}'$ of circles contained in $U$. By the above, each point in $U$ belongs to exactly two circles in $\mathscr{G}'$, except for those points on $C(1/4) - \{O\}$, each of which belongs to exactly one circle in $\mathscr{G}'$. To conclude, we define $\mathscr{F} = \mathscr{G}' \cup \{C(1/4)\}$, which has the desired properties.

Proposition: There is a cover of $\mathbb{R}^2$ with degree $3$.

Proof: Define $C'(r)$ to be the circle of radius $r$ centered at the origin. Let $P = (2, 0)$ and let $U$ be the open disk bounded by $C'(2)$. For each $n \geq 1$, let $\mathscr{H}_n$ be the family of unit circles with centers on $C'(2n+1)$, so if we let $E_n$ be the interior of the region bounded by $C'(2n)$ and $C'(2n+2)$, then each circle in $\mathscr{H}_n$ is contained in $C'(2n) \cup E_n \cup C'(2n+2)$, and each point in $E_n$ belongs to exactly two circles in $\mathscr{H}_n$, while each point on $C'(2n)$ or $C'(2n+2)$ belongs to exactly one circle in $\mathscr{H}_n$. Letting $\mathscr{H} = \bigcup_{n=1}^\infty \mathscr{H}_n$, we see that each point in $\mathbb{R}^2 - (C'(2) \cup U)$ belongs to exactly two circles in $\mathscr{H}$, each point in $C'(2)$ belongs to exactly one circle in $\mathscr{H}$, and each point in $U$ belongs to zero circles in $\mathscr{H}$. To cover $U$, let $\mathscr{F}$ be the family of circles given by the Lemma applied to $U$ and $P$, and define $\mathscr{F}' = \mathscr{F} \cup \mathscr{H} \cup \{C'(2)\}$, so each point of $\mathbb{R}^2$ belongs to exactly two circles in $\mathscr{F}'$, except $P$ which belongs to exactly three (since it lies on $C'(2)$). But none of the circles in $\mathscr{F}'$ are centered at $P$, so we can extend the family $\mathscr{F}'$ to a covering of $\mathbb{R}^2$ with degree $3$ by adding all circles centered at $P$.

Best Answer

Related Solutions

Finding optimal way to steer a system to origin with input constraints

Covering each point of the plane with circles three times

Related Question