26
$\begingroup$

On a unit disk, how should a string of length $2$ be laid in order to minimize $E$, the expected shortest distance between a uniformly random point on the disk and the string?

For example, the diagram below shows an arbitrarily laid string, with two random points on the disk and their shortest distance to the string.

Arbitrary string on disk

Through experimentation, my best effort is the following.

Assuming the equation of the disk's boundary is $x^2+y^2=1$, the equation of the string is $x^2+(y+0.075)^2=\left(\frac{3}{2\pi}\right)^2$, $y>-0.075-\frac{3}{4\pi}$.

So the string is a circular arc with centre $(0,-0.075)$, central angle $\frac{4}{3}\pi$ and arc length $2$.

Circular arc string on disk

With this string, simulations (with two million trials) suggest $E\approx 0.3091$. I do not know how to find the exact value of $E$.

For comparison:

  • If the string is a diameter of the disk, then $E=\int_0^1\int_0^1\sqrt{a}\sin(\pi b)dadb=\frac{4}{3\pi}\approx0.4244$.
  • If the string is a circle concentric with the disk, then $E=\int_0^1\left|\sqrt{x}-\frac{1}{\pi}\right|dx=\frac23+\frac{2}{3\pi^3}-\frac{1}{\pi}\approx 0.3699$.
  • If the string is two sides of an equilateral triangle concentric with the disk, then simulations suggest $E\approx 0.3298$.
  • If the string is a circular arc with central angle $\frac43\pi$ concentric with the disk, then $E=\int_0^1\int_0^1\frac13(p+2q)dadb\approx0.3124$ where $p=\sqrt{\left(\sqrt{a}\cos\left(\frac{\pi}{3}b\right)-\frac{3}{4\pi}\right)^{2}+\left(\sqrt{a}\sin\left(\frac{\pi}{3}b\right)-\frac{3\sqrt{3}}{4\pi}\right)^{2}}$ and $q=\left|\sqrt{\left(\sqrt{a}\cos\left(\frac{\pi}{3}\left(1+2b\right)\right)\right)^{2}+\left(\sqrt{a}\sin\left(\frac{\pi}{3}\left(1+2b\right)\right)\right)^{2}}-\frac{3}{2\pi}\right|$.

Could the optimal string be some other kind of curve, not exactly a circular arc?

One possible approach would be to first consider the string that minimizes the expected shortest distance between a random point on a circle and the string. We can vary the radius of the circle. If we can show that the optimal string is (or is not) a circular arc, then this would suggest that, for the disk, the optimal string also is (or is not) a circular arc.

$\endgroup$
18
  • 2
    $\begingroup$ this is an interesting problem. Maybe the circular arc works because it is the circle inversion of a line segment? $\endgroup$ Commented Nov 2 at 4:33
  • 2
    $\begingroup$ Doing any sort of gradient-based optimization with this looks to be a nightmare due to the optimization subproblem, but something simple like Nelder-Mead could work at the expensive of having to compute the nearest points to some quadrature nodes/MC samples a lot. The upshot is that there are algorithms to do this for polygonal curves very efficiently if they are stored in the proper format $\endgroup$ Commented Nov 2 at 20:08
  • 5
    $\begingroup$ I ran a genetic algorithm to try to find the optimal curve and it seems to support the conjecture that is should be a circular arc. $\endgroup$ Commented Nov 3 at 18:49
  • 2
    $\begingroup$ @Dan, there was a typo. It was supposed to be $\frac{\sqrt{2}}{2\sqrt{2}+1}$. Also, I forgot you introduced me to Desmos in your last question. Thanks for your link. I modified it as per what I intended: desmos.com/calculator/h9qndw70gf?lang=en . AI says that for $Q1$ and $Q2$, the probability is $\lt \sim 0.23$ and for $Q3$ and $Q4$, it is $\lt \sim 0.39$. I averaged the quadrants assuming equal probability of the random point being one of the quadrants and came up with $\sim 0.309$ (after using the more precision of digits from the AI expressions). It uses Monte Carlo. $\endgroup$ Commented Nov 5 at 17:19
  • 2
    $\begingroup$ @Srini I did a rough simulation with your AI-generated string, and I got $E\approx 0.37$. $\endgroup$ Commented Nov 8 at 7:29

1 Answer 1

Reset to default
20
+50
$\begingroup$

Contents

  • Genetic algorithm
  • Result for string of length $2$
  • Upper bound estimate
  • Result for string of length $2\pi$
  • Result for string of length $8\pi$

Genetic Algorithm

I've been running a genetic optimization program with the following procedure:

  1. Create a population of 100 randomly generated piecewise linear curves with 10 points each
  2. Calculate the expected distance to the curve using a sample of 2,000,00 random points (*) uniformly distributed within a unit circle
  3. Pick the string with the lowest expected distance
    • If none of the current generation is better than the string from the previous generation, pick the old string
  4. Create the next generation by making mutated clones of the best string
    • Every 50 generations, before mutating the points, add a new point to every string by bisecting the longest segment.
  5. Go to step 2.

(*) The points are generated once at the beginning of the program and reused for every expected distance calculation. Using a new set of 2,000,000 points each time resulted in a variation of about 0.0002 for the expected distance, making it difficult to optimize.

A mutation occurs by choosing several random points on the string and moving them a small distance in a random direction (2D normal distribution with a width of 0.05 in $x$ and $y$). After every mutation, the line segments are rescaled to keep the total length at 2.

The distance from a random point $P$ in the unit circle to the string is the minimum distance from that point to any line segment. If a line segment is bounded by points $A$ and $B$, then the distance to the segment is calculated like this:

  1. If $\angle ABP > 180^\circ$ use $|B - P|$
  2. If $\angle BAP > 180^\circ$ use $|A - P|$
  3. Otherwise, use the formula for the distance from a point to a line.

Results of string of length $2$

After running for about two hours, it looks like there is a slightly better string than the circular arc. I'll keep this running overnight to see if there are any improvements.

A plot of a string within a unit circle. The string is of length 2 and has 16 points. It is close to circular arc as shown by the overlaid dashed circle. The actual curve seems more oval arc.

The dashed line is the circular arc string from the question. The expected distance to the evolved string is about 0.30876, which I think is sufficiently below the circular arc estimate to call this shape a definite improvement. The evolved shape looks less pointy than an ellipse, so I'll just call it an oval.

The 16 points on this curve are

0.534482028180930824 0.0126067282609719084
0.481792598963642071 -0.0844140913057677134
0.429103169746353375 -0.181434910872507321
0.312359893502933694 -0.300284371336723088
0.290993923754623518 -0.319488836690039579
0.121815046351296696 -0.410847167378589173
0.0228001335821073903 -0.417606597290541393
-0.166624142233877476 -0.37627042911797437
-0.305153136000835101 -0.287553567921906339
-0.387346268908020264 -0.166360175207798666
-0.401712437463491778 -0.118390815418231279
-0.431196829376439494 0.0469926523874151653
-0.406683232078449863 0.179388202292579013
-0.321684078897212067 0.33003966307029492
-0.216886702723406377 0.449164930351805158
-0.136835330525382964 0.514266968314958883

Because it looks cool, here's an animation of the evolution (note that generations with no improvement are skipped).

An animation of the evolution showing the changing shape of the string from a tangled mess to its final partial oval shape.

And a plot of the expected distance improvement.

Plot showing the dropping expected distance as the string evolved.

Zoomed in to show when the circular string was passed.

Same plot as before, but zoomed in to show that the evolved string passed the circular string around generation 80.

Update

After running overnight, I saw a small improvement.

The string:

Updated string with a slightly shirter expected distance. The shape is pretty much the same as the previous one but with 20 points.

The expected distance is about 0.30872 and the string has 20 points. The coordinates of these points are

0.533391056819413567 0.0124396831198378133
0.480802161601850464 -0.0843960159930918219
0.428213266384287305 -0.181231715106021485
0.399594557456859234 -0.215051649851339177
0.290367539567179089 -0.319022227302521499
0.162491717685006865 -0.387255051631992864
0.0532231710520457146 -0.422730426253747682
-0.0326242760244914512 -0.42372015478590136
-0.209809019183051199 -0.358847315372705256
-0.304642042534181756 -0.287147892584144693
-0.386074244415854362 -0.163574665314353662
-0.401017104142071534 -0.118307910859474341
-0.415731171269931032 -0.035773956816425409
-0.430445238397790475 0.0467599972266235231
-0.405978414238562069 0.178902929967859947
-0.363559928912068897 0.254084935190764583
-0.340056481628797924 0.282580853594441128
-0.320171502986650314 0.320900090281686479
-0.21654402591471858 0.44816491087746696
-0.136645395637610578 0.513142730978253359

Looks like this is the best result for a while.

Same as plot before, but this one goes nearly to generation 1500 with no improvement since generation 545.

And the animation:

Updated animation with 2 more similar looking strings at the end.

Upper bound estimate

To estimate the expected distance to the string, imagine that the string of length $L$ runs down a strip of width $W$ and the same length. This strip should cover the whole circle, so $WL = \pi R^2$ where $R$ is the circle's radius. Since the strip covers the whole circle, the points evenly distributed on the circle will be evenly distributed on the strip. The expected distance of the points from the middle of the strip is $E = W/4$. Substituting in $W$ from the area formula gives us our upper bound of the expected distance from a string of length $L$: $$E = \frac W 4 = \frac {\pi R^2} {4 L}$$ For the OP's question, $R = 1$ and $L = 2$, so $E = \frac \pi 8 \approx 0.393$, which is close to but over the value found above. Since this estimate doesn't include the ends of the string, the estimate for $E$ should converge from above to the actual value as the strings get longer.

Result for a string of length $2 \pi$

For longer strings (and especially so for the $8 \pi$ string in the next section), the question becomes how to create the initial string. Any part of the string that is outside the circle plays almost no role in the evolution because there is always a closer part of the string in the circle. So, changes to outside parts of the string have no evolutionary/selection pressure.

If the string is formed randomly, the string will be a tangled mess that will refuse to evolve due to--again--a lack of selection pressure. The animation below shows one such attempt. The string tries to contract itself into the circle, but beyond that, very few changes make much of a difference since the curve is already filling the space.

A tangled mess of a string of length 8 pi

I could define a shape that does fit in the circle like a spiral. But, then the evolution would just optimize the spiral.

Instead, I started with a string of length one and gradually increased its length. The result for a string of length $2 \pi$ is below. The upper bound estimate for $R = 1$ and $L = 2 \pi$ is 0.125.

The final shape of the 2 pi length string. It is a loop near the edge of the circle that turns inwards after most of a loop and circles back the other way closer to the center.

The animation (click if it's not animated):

The 2 pi string animation.

The final points:

-0.789965772315220582 0.0688590194942716588
-0.635123875337368804 0.101269601077341453
-0.493985853928593732 0.130645638974163369
-0.352847832519818605 0.160021676870985313
-0.303247305648016552 0.200761733156218564
-0.182111197105746248 0.234165603974768155
-0.0609750885634759432 0.267569474793317719
0.0696892765059704683 0.225257842126424634
0.20035364157541688 0.182946209459531522
0.245352613251863416 0.0875156225823125189
0.29035158492830998 -0.00791496429490647427
0.220140536672614989 -0.167367653573868125
0.0379025150018416357 -0.246518822098659912
-0.164041863003723476 -0.287426807288701736
-0.333436579037961367 -0.253520148878966955
-0.436038173714576538 -0.269323548712919969
-0.538639768391191653 -0.285126948546873038
-0.657552340533045454 -0.370092816391728863
-0.608572645386628586 -0.474851348002647944
-0.559592950240211717 -0.579609879613567025
-0.407558968378748776 -0.658835809231687053
-0.255524986517285724 -0.738061738849807081
-0.0746515734291436639 -0.759291081048151018
0.0465673478210618386 -0.749292981038678363
0.167786269071267341 -0.739294881029205819
0.318058848732073518 -0.671463518615438182
0.468331428392879945 -0.603632156201670655
0.539943250879664438 -0.52035044427181254
0.611555073366448876 -0.437068732341954369
0.634923502781016946 -0.407093400733237853
0.701955363084923789 -0.289037169824628237
0.768987223388830743 -0.170980938916018593
0.764989637199154915 -0.0659588963881482387
0.760992051009479087 0.0390631461397221089
0.735832472827577799 0.215594173239415737
0.672507312974320093 0.340785228213138613
0.606917034940188893 0.422294793232195875
0.541326756906057804 0.503804358251253137
0.41293101485855499 0.635755882125824789
0.277364799070293211 0.69452495156150118
0.174881037858527294 0.726922934773930329
0.072397276646761391 0.759320917986359589
-0.104261261648935261 0.719734441399556779
-0.175273374080180899 0.740257165838633213
-0.274177504263063532 0.705216043683368099
-0.373081634445946109 0.670174921528103096
-0.519508890409527746 0.581713948810204884
-0.643814586069846095 0.496487084014361646

Result for a string of length $8 \pi$

The final string of length $8 \pi$ is below. The upper bound estimate is 0.3125, so the optimization still had some work to do. It probably would have taken weeks to reach.

The final state of the evolving and growing string with a length of 8 pi.

The animation (click if it's not animated):

The evolution of the 8 pi string.

It's fun to watch these animations since you can see the string being repelled from the circle and itself.

And the points:

-0.908149251548652781 -0.176881493938176176
-0.778626793871330825 -0.465676985193421378
-0.682512702869958021 -0.684954035188139243
-0.328439090906057218 -0.874154212136622921
-0.122821883072939675 -0.991762740828703304
0.0256745801115173394 -0.906629246657542742
0.38277926286730557 -0.875779058402954669
0.629225449164431572 -0.67755563130426133
0.811854941474008496 -0.477252285390701747
0.975870850237779086 -0.0691491271974601918
0.911110709006401009 0.312670013120484258
0.628480503730717177 0.106811104202669815
0.831061822692592211 0.442729790958706459
0.677600131893868696 0.66494113399311694
0.473663184782259938 0.834408273966231295
0.0395878333214256459 0.964427060782276913
-0.224318022527461414 0.897606750852005697
-0.488223878376348397 0.830786440921734481
-0.621863841112510141 0.624361776777709321
-0.910794225817699421 0.397716329896854792
-0.868403915533289772 0.0980158880742023897
-1.00688926037944237 -0.0451930920961402874
-0.850669812067263442 -0.0301756271538094513
-0.787495019909643879 -0.245347094218471229
-0.68080882310702362 -0.471311621928754088
-0.601473856359548531 -0.576800865922418304
-0.492745922845012063 -0.415530250759919229
-0.220052727058845321 -0.2472227368765684
-0.432512820535818188 0.0669135841493738448
-0.285489429198421518 0.177416329514653109
-0.216345263367057339 0.391351048685292247
-0.139767533564176372 0.510267784274085034
0.0734186375176006795 0.756698056174620493
0.228906045923437662 0.520272935054901464
0.234440505407141619 0.286744772398684067
0.239974964890845577 0.0532166097424666557
0.190302620205054729 -0.176720144335227702
0.140630275519263881 -0.406656898412922074
0.287397084141015224 -0.142211082443577719
0.370043485207505574 0.30070630832002887
0.550244973784396962 -0.106755356269265647
0.318460903980199994 -0.304932459940684519
0.211673640105987437 -0.443215966850771803
-0.0351713470739793699 -0.579303629334472991
-0.21365968972578514 -0.730723000236285891
-0.0191553491373940392 -0.708536803585402497
0.232265730846999918 -0.640213533296321358
0.334076115860908462 -0.433361269418278239
0.503778763912004157 -0.322180770740917999
0.710306359249934904 -0.0757110183483790805
0.589137153287516036 0.105887983665537783
0.376932456093719392 0.500092575655710858
0.303662486436242551 0.732325194107754207
-0.11577136693977351 0.732786801559094259
-0.268872408510363425 0.472929612335501792
-0.621432872212348442 0.179496654574041847
-0.499028722639295763 -0.0460765939900202454
-0.39081245082551852 -0.261285740887272411
-0.500415611132677296 -0.306875085289650573
-0.676058616515473609 -0.0915683536031097201
-0.739394083312447825 0.343366686055134318
-0.434796998426337289 0.61109877624297948
-0.222991186144927633 0.827324550126883329
0.144315301558760434 0.844919684688505646
0.309606043204469439 0.79410438796309446
0.521483999927333519 0.652657298089183158
0.60462314947683371 0.350838039466629836
0.729722583997111984 0.183840677333434316
0.881287489971383731 0.0492468906898210212
0.732437782903099133 -0.267055312244513288
0.569077780478930095 -0.532107007526275488
0.453267825816262515 -0.446091851681108542
0.346152492589123228 -0.723518977921642881
0.0354174192135464985 -0.834589583171255756
-0.23327945149758722 -0.80919159047087108
-0.43663053944703023 -0.709714454705183462
-0.231910103804159662 -0.52175314503868242
0.0619273666084603075 -0.39793515511632771
0.0849389659301111044 -0.0252920371155740606
0.0951018196059531251 0.287677131042794909
0.040693390237633062 0.653014066510374636
-0.139540545002996952 0.25715915380750265
-0.206354385281853847 -0.0407516517386351945
-0.0235333376656893037 0.255503454037433686
-0.0602688103265242303 0.0290011303526808983
-0.0970042829873591639 -0.197501193332071889
-0.102696881788194264 -0.271856504404850652
-0.334114115043554316 -0.462843111813585728
-0.527650759375802636 -0.680128221405316369
$\endgroup$
17
  • 2
    $\begingroup$ Great effort and great animation. Horseshoe-ish shape!! $\endgroup$ Commented Nov 10 at 15:10
  • 1
    $\begingroup$ @Dan I updated the result with a very small improvement. $\endgroup$ Commented Nov 10 at 22:59
  • 1
    $\begingroup$ @whpowell96 Can you give me a link to read about those topics? $\endgroup$ Commented Nov 11 at 0:15
  • 1
    $\begingroup$ This Mathoverflow post contains a lot of good references and most numerical analysis books will contain sections on quadrature schemes like this. The Encylopedia of Cubature Formulae is very good. You can either find the linked references or email the guy who runs the site for the password to download the cubature values. You can read the About section for a description of the schemes $\endgroup$ Commented Nov 11 at 1:51
  • 2
    $\begingroup$ @whpowell96 Added results for $8\pi$ string. $\endgroup$ Commented Nov 13 at 9:08

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.