5

I am a biologist studying flight behaviour in the Manx Shearwater. For a project I am doing I am looking at the influence of wind on flight behaviour. I know my birds are within a semi-circle of radius 50km from their nest sites, but I do not know their exact positions. But knowing their position or somewhere close by is important to be able to estimate the wind vectors they are being exposed to.

I am able to acquire six locations of modelled wind data from the Met Office. To make the most of this I want to choose six locations that would enable at least on of these locations to at least be representative of any possible position a bird is at within this semi-circle. So I imagine there is an optimal distribution of the 6 locations within this semi-circle that minimises the maximum distance a bird could be from any one location. I have a possible way of working out this distribution below and it would be very much appreciated if anyone could comment on the suitability of this method or come up with any other methods that would enable a solution to the problem. Thank you.

Let $S$ be the unit semicircle in the plane.

We want to find points $x_1$, $x_2$, $x_3$, $x_4$, $x_5$, $x_6$ in $S$ so as to minimise $\max\{\min\{d(x,x_1), ... ,d(x,x_6)\} : x \in\ S\}$.

James Kempton
  • 51
  • 2
    To transcribe your problem: You want to cover a semicircle with six circles of minimal radius. I don't think you will find an exact solution, but with a computer you should be able to find an approximative solution. – Dominik Sep 18 '15 at 15:45
  • When you try to formulate this as an optimization problem, it becomes a max-min problem. You can solve this by converting your problem into LP as: max z subject to z <=d(x,x1) z <=d(x,x2)... – Sriharsha Madala Sep 18 '15 at 21:14

1 Answers1

1

As stated in the comment by Dominik the problem can be formulated as finding a coverage of a semicircle with 6 congruent circles with minimal radius. Well, here is a pretty good, maybe even optimal configuration (the figure shows three circles covering half of the semicircle, the other three circles are symmetric by the axis of symmetry of the semicircle):

enter image description here

Let $AB$ be the bounding diameter of the semicircle and $C$ its center. The covering circles have a radius $$r = \frac{-2+\sqrt{2}+\sqrt{2 \sqrt{2}-2}}{2 (\sqrt{2}-1)} R \approx 0.39158\ R,$$ where $R=AC=BC$ is the radius of the semicircle. The centers of the covering circles lie on radii with angles $\frac{\pi}{8},\frac{\pi}{4},\frac{3\pi}{8},\frac{5\pi}{8},\frac{3\pi}{4},\frac{7\pi}{8}$ to the bounding diameter. The centers of the two "inner" circles (at angles $\frac{\pi}{4}$ and $\frac{3\pi}{4}$) have a distance of $r\approx 0.39158\ R$ from $C$. The centers of the four "outer" circles (at angles $\frac{\pi}{8},\frac{3\pi}{8},\frac{5\pi}{8},\frac{7\pi}{8}$) have a distance $\frac{R}{\sqrt[4]{2}} \approx 0.8409\ R$ from $C$.

The above configuration is obviously a local optimum; currently I cannot prove that it is a global optimum, though. Following is a sketch of the construction/computation.

enter image description here

Let $CD$ be the radius of the semicircle which is perpendicular to the bounding diameter $AB$. Let $F$ be the center of an "inner" circle; by construction we have $\angle FCD = \frac{\pi}{4}$. This circle intersects the radius $CD$ at $G$ a second time. With $FC=FG=r$ we have $CG = r\sqrt{2}$.

Let $H$ be the center of an "outer" circle with $\angle HCD = \frac{\pi}{8}$ and $HG=HD=r$. And let $I$ be the midpoint of $GD$. Hence $$CI = CG+GI = CG + (R-CG)/2 = (R+CG)/2 = (R+r\sqrt{2})/2$$ and $$HI^2 = HG^2-GI^2 = r^2-((R-CG)/2)^2 = r^2-((R-r\sqrt{2})/2)^2.$$ From $HI/CI=\tan \frac{\pi}{8} = \sqrt{2}-1$ one can compute $$r = \frac{-2+\sqrt{2}+\sqrt{2 \sqrt{2}-2}}{2 (\sqrt{2}-1)} R.$$

coproc
  • 1,538