{"id":2582,"date":"2018-12-08T12:09:26","date_gmt":"2018-12-08T18:09:26","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2582"},"modified":"2018-12-08T20:09:41","modified_gmt":"2018-12-09T02:09:41","slug":"settlers-in-a-circle","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/settlers-in-a-circle\/","title":{"rendered":"Settlers in a circle"},"content":{"rendered":"

In this Riddler problem<\/a>, the goal is to spread out settlements in a circle so that they are as far apart as possible:<\/p>\n

\nAntisocial settlers are building houses on a prairie that\u2019s a perfect circle with a radius of 1 mile. Each settler wants to live as far apart from his or her nearest neighbor as possible. To accomplish that, the settlers will overcome their antisocial behavior and work together so that the average distance between each settler and his or her nearest neighbor is as large as possible.<\/p>\n

At first, there were slated to be seven settlers. Arranging that was easy enough: One will build his house in the center of the circle, while the other six will form a regular hexagon along its circumference. Every settler will be exactly 1 mile from his nearest neighbor, so the average distance is 1 mile.<\/p>\n

However, at the last minute, one settler cancels his move to the prairie altogether (he\u2019s really antisocial). That leaves six settlers. Does that mean the settlers can live further away from each other than they would have if there were seven settlers? Where will the six settlers ultimately build their houses, and what\u2019s the maximum average distance between nearest neighbors?<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

I approached this problem from a modeling and optimization perspective. If there are $N$ settlers and we imagine the coordinates of the settlers are $(x_i,y_i)$ for $i=1,\\dots,N$ and $d_i$ is the distance between the $i^\\text{th}$ settler and its nearest neighbor, then we can model the problem as follows:
\n\\[
\n\\begin{aligned}\\underset{x,y,d\\,\\in\\,\\mathbb{R}^N}{\\text{maximize}} \\quad & \\frac{1}{N}\\sum_{i=1}^N d_i \\\\
\n\\text{such that} \\quad & x_i^2 + y_i^2 \\le 1 &&\\text{for }i=1,\\dots,N\\\\
\n& (x_i-x_j)^2 + (y_i-y_j)^2 \\ge d_i^2 &&\\text{for }i,j=1,\\dots,N\\text{ and }j\\ne i
\n\\end{aligned}
\n\\]The objective is to minimize the average distance between each settler and its nearest neighbor (the average of the $d_i$). The first constraint says that each settler must be within the circle (a distance of at most $1$ from the origin). The second constraint says that the $i^\\text{th}$ settler is a distance at least $d_i$ from each of the other settlers.<\/p>\n

The game is then to find $(x_i,y_i,d_i)$ that satisfy these constraints and maximize the objective. Broadly speaking, this is an example of a mathematical optimization problem<\/a>. Unfortunately, the problem as stated is nonconvex<\/a> problem because of the form of the second constraint. This means that the problem may have local maximizers that are not globally optimal. There are two ways forward:<\/p>\n

First, we could use local search: start with randomly placed settlers, wiggle their positions in ways such that the objective continues to increase, and then stop once we can no longer improve the objective. Examples of such approaches include hill-climbing<\/a> and interior-point methods<\/a>. In general, such approaches only find local maxima, so we should try many random starting positions to ensure we find the best possible answer.<\/p>\n

Second, we could use global search: these are methods that attempt to find a globally optimal solution by considering many configurations simultaneously and adding random perturbations that can “kick” a solution out of a local maximum. Examples include simulated annealing<\/a> and particle swarms<\/a>. These approaches tend to be much slower than local search, but they have a much better chance of finding a global optimum.<\/p>\n

Ultimately, I used local search with several random initializations. Here is how the maximum average distance scales with the number of settlements.<\/p>\n

\"\"<\/a><\/p>\n

The bar plot also shows how well we would do if we distributed the settlements evenly on the circumference (“all on the border”) and if we put one in the middle and the rest evenly distributed on the circumference (“one in the center”). We can also examine what the settlement distributions actually look like. Here they are:<\/p>\n

\"\"<\/a><\/p>\n

The case $N=6$ is particularly interesting because it has a settlement that is almost<\/em> in the center, but not quite. Indeed, the average minimum distance to neighbors for this case is $1.002292$, so we benefit ever so slightly by placing one settlement off-center.<\/p>\n

We can solve for the $N=6$ case analytically as well, but the solution isn’t pretty (fair warning!) It turns out the settlements are distributed throughout the circle in the following way:<\/p>\n

\"\"<\/a><\/p>\n

Here, $x$ is the distance between the origin and the point $A$. The other distances satisfy $z \\lt y \\lt x+1$, and the average distance to the nearest neighbor is therefore $\\tfrac{1}{6}(1+x+2y+3z)$. Note that once we set $x$, this uniquely determines the positions of all the other points. After some messy trigonometry, we obtain the following equations relating $x$, $y$, $z$ and two auxiliary variables $p$ and $q$:
\n\\begin{align}
\ny^2&=1+x-x^2-x^3\\\\
\nz^2&=1-x^2+2x\\left(pq-\\sqrt{1-p^2}\\sqrt{1-q^2}\\right) \\\\
\np&= \\tfrac{1}{2}(1-2x-x^2)\\\\
\nq&= \\tfrac{1}{2}(1-x+x^2+x^3)
\n\\end{align}We can eliminate $\\{y,z,p,q\\}$ and solve for the average distance $\\bar d = \\frac{1+x+2y+3z}{6}$ as a function of $x$ alone:
\n\\[
\n\\bar d = \\frac{x+1}{12} \\left(2+4 \\sqrt{1-x}+3 \\sqrt{2}\\sqrt{1-x} \\sqrt{\\left(x^3+2 x^2-x+2\\right)-x \\sqrt{x+3} \\sqrt{x^3+x^2-x+3}} \\right)
\n\\]We can then plot this function of $x$, and we get the following curve:<\/p>\n

\"\"<\/a><\/p>\n

Interestingly, this function reaches its maximum just a bit after $x=0$. Zooming in, we can see more clearly:<\/p>\n

\"\"<\/a><\/p>\n

The maximum occurs at about $x=0.0555108$ and the maximum value is $1.00229$, just as we found before. If we try to solve for this analytically by taking the derivative of this function, setting it equal to zero, and eliminating rationals, we obtain the following result… That the optimal $x$ a root of the following $30^\\text{th}$ order polynomial:
\n\\begin{align}
\nx^{30}&+\\tfrac{152}{9} x^{29}+\\tfrac{9259}{81} x^{28}+\\tfrac{6851}{18} x^{27}+\\tfrac{383363 }{648}x^{26}+\\tfrac{1999495} {5832}x^{25}\\\\
\n&+\\tfrac{43478263}{52488} x^{24}+\\tfrac{75726373}{23328} x^{23}+\\tfrac{3282369305}{1679616} x^{22}-\\tfrac{31642768891}{7558272} x^{21}\\\\
\n&+\\tfrac{367775655235}{136048896} x^{20}+\\tfrac{392027905801}{34012224} x^{19}-\\tfrac{2016793647847}{136048896} x^{18}-\\tfrac{1258157703385}{68024448} x^{17}\\\\
\n&+\\tfrac{4545130566235}{136048896} x^{16}-\\tfrac{22059424877}{17006112} x^{15}-\\tfrac{8448216227365}{136048896} x^{14}+\\tfrac{2878062707167}{68024448} x^{13}\\\\
\n&+\\tfrac{7398046956073}{136048896} x^{12}-\\tfrac{312655708903}{3779136} x^{11}+\\tfrac{17266856539}{1679616} x^{10}+\\tfrac{63670102441}{839808} x^9\\\\
\n&-\\tfrac{29827845749}{559872} x^8-\\tfrac{541401565}{23328} x^7+\\tfrac{619158287}{23328} x^6+\\tfrac{6168305}{2592} x^5\\\\
\n&-\\tfrac{156285}{32} x^4-\\tfrac{5153}{36} x^3+\\tfrac{3923}{12} x^2+\\tfrac{45}{2} x-\\tfrac{35}{16}
\n\\end{align}Yuck! Here is what you get if you plot this polynomial; as expected, there is a root at $x=0.0555108$.<\/p>\n

\"\"<\/a><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

In this Riddler problem, the goal is to spread out settlements in a circle so that they are as far apart as possible: Antisocial settlers are building houses on a prairie that\u2019s a perfect circle with a radius of 1 mile. Each settler wants to live as far apart from his or her nearest neighbor … Continue reading “Settlers in a circle”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2599,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[28,10,31,26,2],"class_list":["post-2582","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-calculus","tag-geometry","tag-modeling","tag-optimization","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2582","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2582"}],"version-history":[{"count":9,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2582\/revisions"}],"predecessor-version":[{"id":2606,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2582\/revisions\/2606"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2599"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}