5
$\begingroup$

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 one 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),\ldots ,d(x,x_6 )$}:$x∈ S$} .

$\endgroup$

migrated from physics.stackexchange.com Sep 18 '15 at 21:12

This question came from our site for active researchers, academics and students of physics.

  • $\begingroup$ This seems to be more of a mathematics optimization problem than physics. Also, is there a typo in your minimization statement at the end. You want to minimize max{min{...}}? $\endgroup$ – Bill N Sep 18 '15 at 21:09
  • $\begingroup$ It's not clear how you can do better than just equally spacing the points. By the sound of it, you want to do the optimization over uniformly random $x$ contained say, somewhere in a large circle of radius $R$. Then the answer should be uniformly spaced points. $\endgroup$ – Alex R. Sep 18 '15 at 21:31
  • $\begingroup$ I'd let a computer do it :-) . Write an equation for the state , i.e. y = min(all the distances), take the 6-dimensional gradient, and find the zeros. The tricky part is applying the boundary conditions to stay within the semicircle. However, I need to ask: have you verified the size of uniform wind patterns? If the "patches" of uniform wind are smaller than 1/6 the total area, your setup will fail. $\endgroup$ – Carl Witthoft Sep 18 '15 at 21:48
  • $\begingroup$ I would caution that "minimizing the max distance" may not be the optimal strategy. You really want to minimize the error in your estimate of wind; this relates not only to the distance to the nearest measurement. You might consider how interpolation between two points will improve your accuracy, while extrapolation makes it worse. That would change your optimization criteria. $\endgroup$ – Floris Sep 18 '15 at 23:03
  • $\begingroup$ A simpler way to phrase your problem is: what is the smallest radius such that one can cover the semicircle with 6 discs, and where should I put them? $\endgroup$ – Mariano Suárez-Álvarez Sep 20 '15 at 22:34
3
$\begingroup$

I wrote a program (C++ source here) to randomly move 6 points inside a unit-radius semicircle to find the set with the minimum-maximum-minimum distance to the points.

The points are:

  • $x_1 = (0.00369774,\ 0.102314) $
  • $x_2 = (-0.0104503,\ 0.776634)$
  • $x_3 = (0.486772,\ 0.613544 )$
  • $x_4 = (-0.495982,\ 0.599445)$
  • $x_5 = (0.681082,\ 0.194028 )$
  • $x_6 = (-0.678082,\ 0.185806 )$

Plot of points

The furthest that any point inside the semicircle can get from these points is $0.372701$. These points could be refined by noting that $x_1$ and $x_2$ should lie on the y-axis and the pairs $x_3/x_4$ and $x_5/x_6$ should be reflections about the y-axis. (I may do this later and update this answer.)

Multiply all of the coordinates by 50 km to get the distances in your region.

  • $x_1 = (0.1849 , 5.1157)$
  • $x_2 = ( -0.5225, 38.8317)$
  • $x_3 = (24.3386 , 30.6772)$
  • $x_4 = (-24.7991 , 29.9722)$
  • $x_5 = (34.0541 , 9.7014)$
  • $x_6 = (-33.9041 , 9.2903)$

The farthest any bird could be from any point in the semicircle is $50\ km\times 0.372701 = 18.6\ km$).

Update

I reran the program with the symmetry constraints and came up with an improved set of points for the unit semicircle:

  • $x_1 = (0,\ 0.127093) $
  • $x_2 = (0,\ 0.772431)$
  • $x_3 = (0.51494,\ 0.620379 )$
  • $x_4 = (-0.51494,\ 0.620379)$
  • $x_5 = (0.675,\ 0.179963 )$
  • $x_6 = (-0.675,\ 0.179963 )$

These points have a maximum minimum distance of 0.371499. The plotted points will look nearly identical to the above picture, so there's no need for a new plot.

Update 2

Now with a better minimax distance measurement function, I get results pretty much indistinguishable from achille hui's much more thorough answer. The functions I use are pretty much transcribed directly from paper-and-pencil work, so there are probably numerical stability/precision issues, which is why there are always tiny gaps in the areas covered. Anyway, the points:

  • $x_1 = (0,\ 0.780365)$
  • $x_2 = (0,\ 0.135024 )$
  • $x_3 = (0.673298,\ 0.177718 )$
  • $x_4 = (-0.673298,\ 0.177718 )$
  • $x_5 = (-0.519825,\ 0.619597 )$
  • $x_6 = (0.519825,\ 0.619597)$

Maximum distance from any point: $0.371939$.

Semicircle with 6 points

Update 3 (nope, see next update)

It seems that symmetrical arrangements are not ideal. This is more like circle packing in a finite region, so regular structures are not generally the solution. So, here's a rerun with no symmetry constraints and full precision on the coordinates and distances:

  • $x_1 = (0.011215967925017974,\ 0.77770753298823792)$
  • $x_2 = (-0.0050407262850791544,\ 0.135824787460115)$
  • $x_3= (0.52656994142649183,\ 0.61219920048310006)$
  • $x_4 = (-0.51563560969298672,\ 0.63132516707874731)$
  • $x_5 = (0.67061696937131543,\ 0.17280432767295217)$
  • $x_6 = (-0.67565769565639455,\ 0.18208950036099866)$

Maximum distance to any point = $0.37196036956729422$

Updated C++ source code can be found here: http://pastebin.com/ak9Dc0Dm

Update 4

I didn't even notice that my Update 3 result was worse than Update 2. With that in mind, here's another run with symmetry and full precision output that beats every previous result:

  • $x_1 = (0,\ 0.77717381888117043)$
  • $x_2 = (0,\ 0.13430201651894846)$
  • $x_3 = (0.67341550527614757,\ 0.17796444941964365)$
  • $x_4 = (-0.67341550527614757,\ 0.17796444941964365)$
  • $x_5 = (-0.52004110089103339,\ 0.62151297704900443)$
  • $x_6 = (0.52004110089103339,\ 0.62151297704900443)$

Maximum distance to any point = $0.37192577249511566$.

C++ code here: http://pastebin.com/Yrqry5H1

$\endgroup$
  • $\begingroup$ By perturbing your data set to make the corners of Voronoi cells touches the semi-circle. Following data set $$\begin{cases} x_1 &= (0,0.13121005),\\ x_2 &= (0,0.76614727),\\ x_{3,4} &= (\pm 0.51983971,0.62791492),\\ x_{5,6} &= (\pm 0.67403990,0.17923625) \end{cases}$$ can bring the upper bound of minimal maximum distance down to around $0.37198874$. $\endgroup$ – achille hui Sep 19 '15 at 17:51
  • $\begingroup$ What do you get for 7 points? $\endgroup$ – Ed Pegg Sep 21 '15 at 15:25
  • $\begingroup$ The new set seems incorrect, it misses some points on the boundary. For example, the circles of radius 0.371499 centered at $x_3$ and $x_5$ intersect at $\approx (0.865927626561528,0.4986448922006425)$ which is at a distance $\approx 0.9992384014639707 < 1$ from the center. The circles fail to cover a tiny "triangle" near these sort of points... $\endgroup$ – achille hui Sep 21 '15 at 18:02
  • $\begingroup$ Hmm... looks like the candidate for minimal maximum distance has a closed form expression: $$r = \sqrt{3 + 2\sqrt{3} - 2\sqrt{5 + \sqrt{27} - \frac{1}{\sqrt{27}}}} \approx 0.3719887399641695$$ $\endgroup$ – achille hui Sep 21 '15 at 21:06
  • $\begingroup$ @achillehui You're right about the gaps wherever three circles intersect. I'll have to adjust my algorithm. Then again, for the purposes of the OP's question, I think the gaps are small enough to not matter. $\endgroup$ – Mark H Sep 21 '15 at 23:09
2
$\begingroup$

Notes

The explicit form of the lower bound in this answer may be wrong. In the updated numerical results from Mark, it can produce a configuration with a $r$ smaller than the lower bound here. It looks like the constraint on one of the points (the most likely candidate is point $F$) is redundant. We are essentially back to square one.... C'est la vie....


Please consider this as a supplement to Mark H's answer.

In Mark's answer, the centers are roughly symmetrical in the horizontal direction. If one compute the Voronoi diagram associated with these centers, one obtain a figure looks roughly what is shown below.

$\hspace0.75in$ Voronoi diagram in first quadrant

The points $A, B, C, D$ are those $4$ centers in the first quadrant. The orange lines are the boundary of the Voronoi cells. The points $E, F, G, H, I$ are the intersections of the boundaries of these cells and the semi-circle. Let $O = (0,0)$ and $X = (1,0)$.

The key observation is the distances (those illustrated in pink) among these points are all roughly equal. If the algorithm in Mark's answer converge to some configuration of centers, that configuration should be a local minimum of the maximum-minimum distance functional. This means these distances should be equal to each other exactly. i.e.

$$|AX| = |AE| = |AF| = |AG| = |BE| = |BF| = |BH|\\ = |CF| = |CG| = |CH| = |CI| = |DH| = |DI|$$

To find such a configuration, we first relax the constraint that $D$ lies on $y$-axis. We assume $A$ is located near what's in Mark's answer.

Let $r$ be the common values of above $13$ distances. Let $A = (1-u,v)$ and $B = (0,w)$. The condition $|AX| = r$ leads to $r^2 = u^2 + v^2$. We then proceed to express the positions of $E, F, G, C, H, I$ (in that order) and finally $D$ in terms of these 3 variables $u,v,w$.

Aside from the formula of $I$ and $D$, they are not that horrible.

  • $|AE| = r$ implies $E = (1-2u,0)$.
  • $|BE| = r$ leads to $$w^2 + (1-2u)^2 - u^2 - v^2 = 0\tag{*1}$$
  • $|AE| = |BE| = |AF| = |BF|$ implies $F = A + B - E = (u,v+w)$.
  • $|AX| = |GX|$ and $|OX| = |OG|$ implies $$G = \verb/Refl/(A,X) = \left(\frac{2(1-u)^2}{v^2+(1-u)^2}-1,\frac{2(1-u)v}{v^2+(1-u)^2}\right)$$ where $\displaystyle\;\verb/Refl/(\vec{U},\vec{V}) = 2\frac{\vec{V}\cdot\vec{U}}{|\vec{U}|^2}\vec{U} - \vec{V}$ maps point $V$ to its mirror image with respect to $OU$.
  • $|AF| = |AG| = |CF| = |CG|$ implies $$C = F + G - A = \left(\frac{2(1-u)^2}{v^2+(1-u)^2}+2u-2,w+\frac{2(1-u)v}{v^2+(1-u)^2}\right)$$
  • $|BF| = |BH| = |CF| = |CH|$ implies $$H = B + C - F = \left(\frac{2(1-u)^2}{v^2+(1-u)^2}+u-2,w+ \frac{2(1-u)v}{v^2+(1-u)^2}-v\right)$$

  • $|CG| = |CI|$ and $|OG| = |OI|$ implies $ I = \verb/Refl/(C,G) = $ a horrible mess!

  • $|CH| = |CI| = |DH| = |DI|$ implies $D = H + I - C = $ another horrible mess!

If we put back the constraint that $D$ lies on the $y$-axis, we obtain

$$((u-1)v^2+u^3-u^2-u+1)w^2 + (4u^2-8u+4)vw\\ + (4u^3-4u^2-4u+4)v^2 + 4u^5-12u^4+12u^3-4u^2\\ = 0\tag{*2}$$ We can eliminate $w$ by computing the resultant between the two polynomials in $(*1)$ and $(*2)$.
The resultant has the form $(u-1)^2f(u,v)$ where $f(u,v)$ is a polynomial of degree $8$ in $u, v$.
We can simplify this expression a little bit by a change of variable. Let $(u,v) = (rs, r\sqrt{1-s^2})$,
the condition becomes

$$\begin{align} g(r,s) \stackrel{def}{=} &\;\; f(rs,r\sqrt{1-s^2})\\ = &\;\;16r^6s^4+(-16r^7-32r^5-16r^3)s^3+(24r^6+48r^4+24r^2)s^2\\ &\;\; + (8r^7-24r^5-40r^3-8r)s+r^8-12r^6+22r^4+4r^2+1\\ = &\;\; 0 \end{align} $$ To complete our task, we need to find the point along the curve $g(r,s) = 0$ with minimal $r$. At that point, the tangent vector of the curve will be pointing in the $s$-direction. This means $\frac{\partial g}{\partial s}(r,s) = 0$ at that particular point. We can eliminate $s$ by computing the resultant between $g(r,s)$ and $\frac{\partial g}{\partial s}(r,s)$. The resultant is reasonably simple

$$-1048576 r^{18} (r^2-1)^{12} (27r^8 - 324 r^6 - 270 r^4-36 r^2 + 11)$$

Eliminating the impossible values $0$ and $1$ for $r$, the local extremium of maximum-minimum distance functional should be a root of the quartic equation: $$27r^8 - 324 r^6 - 270 r^4-36 r^2 + 11 = 0$$ Solving this equation and compare the numerical values we find from Mark's answer, the $r$ we seek equals to

$$r = \sqrt{ 3 + 2\sqrt{3} - 2\sqrt{5 + \sqrt{27} - \frac{1}{\sqrt{27}}}} \approx 0.3719887399641683$$ and at the least, this is a local minimum for the maximum-minimum distance functional. With this, we can numerically back out the parameters $u,v,w$

$$\begin{cases} u &\approx 0.3259601005065833\\ v &\approx 0.1792362562035586\\ w &\approx 0.1312100460994327 \end{cases}$$

and the location of the centers

$$\left\{\begin{array}{lcll} x_5 \leftrightarrow A & \approx & (0.6740398994934167,& 0.1792362562035586),\\ x_1 \leftrightarrow B & \approx & (0,& 0.1312100460994327),\\ x_3 \leftrightarrow C & \approx & (0.5198397097356646, & 0.6279149145866445),\\ x_2 \leftrightarrow D & \approx & (0,& 0.7661472706667444) \end{array}\right.$$

$\endgroup$
  • $\begingroup$ Glad I was able to inspire this answer! $\endgroup$ – Mark H Sep 22 '15 at 13:29
  • $\begingroup$ I've updated my answer. It looks like symmetrical arrangements are not optimal. $\endgroup$ – Mark H Sep 23 '15 at 7:35
  • $\begingroup$ @MarkH Yup, it looks like symmetrical arrangement may not be the optimal one. However, if it is not, then it is sort of strange why you still get a number so close to mine. One possibility is we have been trapping near some sort of saddle point.... $\endgroup$ – achille hui Sep 23 '15 at 7:45
  • $\begingroup$ Actually, I was wrong. Symmetrically constrained points give better results. I updated my answer again. $\endgroup$ – Mark H Sep 23 '15 at 8:01
  • $\begingroup$ I think you're right about point $F$. In my results, the circles don't meet at a point near $F$. There's a triangular area of overlap instead of a point. $\endgroup$ – Mark H Sep 23 '15 at 8:05
0
$\begingroup$

For six points in a unit semicircle, the answer is pretty boring, with a maximal minimum distance of $\sqrt{2-\sqrt2} = 0.765367...$

semicircle 6

For seven points, the problem gets interesting, with a maximal distance somewhere over $0.679316$.

semicircle 7

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.