Page 1 of 1

### Fitting circles under a curve

Posted: Mon May 28, 2012 11:04 am UTC
I thought of a problem a few days ago and I have no idea as to its solution. I posted this on Reddit earlier today but I figured people here could help. Suppose you have a boundary formed by the curve y=e^(-x), and the lines x=0 and y=0. In this boundary you place the largest possible circle you can, which touches the y-axis, the x-axis and y=e^(-x). You then place the next largest possible circle to the right of this one, which touches the first circle, y=e^(-x) and the x-axis. This process is repeated indefinitely. If there are an infinite number of circles formed in this way, what is the sum of their areas?

I suspect that the answer will be pretty complicated. Just working out the x-value of the point at which the first circle touches the curve involves working out an x such that x-sqrt((1+e^(2x))x^(2))+sqrt(2xe^(3x))-e^(x)=0, which is a transcendental equation.

Thanks.

### Re: Fitting circles under a curve

Posted: Mon May 28, 2012 7:44 pm UTC
That looks pretty tough, I think your best bet would be to try and see if the area of the circles forms a geometric series, which seems very unlikely, and then area would be related to the area of the first circle, being transcendental.. If it's not geometric then it is very unlikely you will come across a series that you can even manage to describe, not to mention sum. Perhaps instead of getting the circles to touch, at the leftmost point of the previously made circle put down an axis parallel to the y axis, and see if continuing that process is equivalent to getting the circles to touch, or somehow related... An idea that I have no clue how to implement would be to calculate the density that the circles fill the curve e^-x in the desired area, and multiply that by, well, just 1! Good luck, though I doubt it is doable, unless there is some neat trick I don't know...

### Re: Fitting circles under a curve

Posted: Tue May 29, 2012 11:27 pm UTC
After an absolutely horrible derivation which I have not the patience to post I've got the x value for the point of intersection between the first circle and the curve e^-x as satisfying the equation (x-a)^3 + (x-a)^2 + (x-a) - a^2 = 0 where a is the x coordinate of the centre of the circle.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 2:22 am UTC
Are you sure that's right, Timefly? I got the intersection of the circle and curve to be approx. x=0.498 and the centre of the circle at x=0.328. Here's what I did:

The cirle has radius r, and has been shifted r right and r up. We have r^2=(x-r)^2+(y-r)^2, which can be rearranged to give y=r+sqrt(2rx-x^2). We equate the value at the point of intersection for both equations and the derivative at that point, to give equations -e^(-x)=(x-r)/sqrt(2xr-x^2) as well as r^2=(e^(-x)-r)^2+(x-r)^2, which can be manipulated to give x-sqrt(x^2(e^(2x)+1))=e^x-sqrt(2xe^(3x)). Wolfram alpha gives approximately x=0.498 and r=0.328. x and r don't seem to satisfy the relation (x-r)^3 + (x-r)^2 + (x-r) - r^2 = 0.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 2:36 am UTC
I think it should be
0 = (x-a)3+2(x-a)2+(x-a)-a2(x-a)-2a2.

Another (somewhat more compact but still transcendental) equation for x is
4x cosh x = (1+x)2.
I don't have anything interesting to say about the full problem, though; it looks ugly.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 3:38 am UTC
It doesn't actually look too bad. The first circle is essentially arbitrary. Once you find the second circle, similarity should solve the whole thing.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 3:50 am UTC
Ben-oni wrote:It doesn't actually look too bad. The first circle is essentially arbitrary. Once you find the second circle, similarity should solve the whole thing.

I don't think the areas of the circles form a geometric series because their centers get closer as you add more.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 4:00 am UTC
Yeah, they don't form a geometric progression. If they did, their centres would be on a straight line.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 7:12 am UTC
Ah, right. It only scales in one direction. I guess I was mentally filling it in with ellipses.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 7:16 am UTC
Randommelon wrote:Are you sure that's right, Timefly? I got the intersection of the circle and curve to be approx. x=0.498 and the centre of the circle at x=0.328.

Now you say that, I think I've found a mistake in my working.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 7:32 am UTC
Timefly wrote:
Randommelon wrote:Are you sure that's right, Timefly? I got the intersection of the circle and curve to be approx. x=0.498 and the centre of the circle at x=0.328.

Now you say that, I think I've found a mistake in my working.

Yeah, eta oin shrdlu says it should be 0 = (x-a)^3+2(x-a)^2+(x-a)-a^2(x-a)-2a^2, which works when you put x=0.498.

I don't know much about it, apart from what I've read on Wikipedia, but would it be possible to express the radius or point of intersection explicitly using Lambert's W function or some other special function? I'm guessing not, seeing how Wolfram Alpha managed to miss it.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 7:48 am UTC
If an is the radius of the nth circle, then for large n
(1/an) - (1/an-1) ≈ 2.
This can be used to get good estimates for the tail of the sequence, e.g. if you want to numerically find the area covered by all of the circles.

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 9:45 am UTC
eta oin shrdlu wrote:If an is the radius of the nth circle, then for large n
(1/an) - (1/an-1) ≈ 2.
This can be used to get good estimates for the tail of the sequence, e.g. if you want to numerically find the area covered by all of the circles.

Might I ask how you derived this?

Also, if a circle touches e^(-x) at x then its radius r is 2cosh(x)-sqrt(e^(2x)+1).

### Re: Fitting circles under a curve

Posted: Wed May 30, 2012 7:17 pm UTC
Randommelon wrote:
eta oin shrdlu wrote:If an is the radius of the nth circle, then for large n
(1/an) - (1/an-1) ≈ 2.
This can be used to get good estimates for the tail of the sequence, e.g. if you want to numerically find the area covered by all of the circles.

Might I ask how you derived this?
Here's an informal argument.

For large x, y=e-x<<1, so the radius a of the circle tangent at (x,y) is a≈y/2. The next circle to the right will be at roughly x'≈x+2a and so will have roughly the same radius, a'≈y'/2≈y/(1+2a)/2=a/(1+2a) [using y'=e-x'≈e-x-2a≈y/(1+2a)]. So
1/a' ≈ (1+2a)/a = 1/a + 2.

----

This can all be formalized, turning all of the ≈ into inequalities or O(yk) error terms depending on your preferences; but the formal derivation doesn't have any surprises. You just start with equations giving the position of the next circle in terms of the current circle parameters, find bounds for the changes, and then do Taylor expansions to first nontrivial order in y. The equations I started from are
y = e-x [equation of curve]
0 = (x-u)2 + y2 - 2ay [circle touches curve]
0 = (x-u) + ay - y2 [circle tangent to curve]
4a0a = (u-u0)^2 [circle tangent to previous circle]
where this circle is centered at (u,a) with radius a, touches the curve at (x,y), and the previous circle is centered at (u0,a0) with radius a0. [You can solve the second and third equations for a to get your equation for radius.]

### Re: Fitting circles under a curve

Posted: Thu May 31, 2012 5:33 am UTC
Is there a closed form expression for the same scenario but with squares instead of circles? It's much easier to derive the equation (a(0) = 0, a(n) = W(e^(a(n - 1))) + a(n - 1)) but the sum seems to converge very slowly (maybe my implementation of the lambert W function is just inefficient). I get something around 0.824.

### Re: Fitting circles under a curve

Posted: Mon Jun 04, 2012 1:49 pm UTC
nadando wrote:Is there a closed form expression for the same scenario but with squares instead of circles? It's much easier to derive the equation (a(0) = 0, a(n) = W(e^(a(n - 1))) + a(n - 1)) but the sum seems to converge very slowly (maybe my implementation of the lambert W function is just inefficient). I get something around 0.824.

Convergence is slow in both the original version and in your square version because for large n each circle (or square) is roughly the same size as its neighbours, which is a consequence of the fact that the slope of e-x soon becomes rather close to zero.

It's not easy to get accurate sums of such series: rounding errors soon swamp the true value, unless you're using a high precision math package.

Here's a PostScript file that illustrates the circular case, showing the first 34 circles. The circle coordinates were calculated in Python, using mpmath. I haven't bothered to calculate the cumulative area sum yet. FWIW, mpmath has a good implementation of the Lambert W function.

Code: Select all

`%!PS-Adobe-3.0%%BoundingBox:  0 0 1500 500%%Title: (Exponential Circles)%%Creator: (PM 2Ring)%%Creationdate: (19:43:00 June 4 2012)%%Pages: 1%%EndComments%With fine subdivisions24 dict begin%Custom page size/XM 1500 def/YM 500 def%bottom left of printable area/XL 20 def/YL 40 def/e 2.718281828459045 def%the function to plot: y = e^x/Func{    e exch neg exp} bind def%Function bounds, axes & axis label increments/xlo 0.0 def/xmin xlo def%/xmin 0 def/xa 0 def/xhi 3.55 def/xd .1 def/ylo 0.0 def/ya 0 def/yhi 1.05 def/yd .1 def%Function evaluation increment/dd .005 def% Minor grid increment multipliers/xdd .2 def/ydd .2 def/xr xhi xlo sub def/yr yhi ylo sub def% ------------------------------------------------------------%font/FS 12 def/FONTNAME%/Palatino-Roman/Times-Romandef/HEADING (Exponential Circles) def% ------------------------------------------------------------/nstr 10 string def%centered text display/Cshow{    gsave        dup stringwidth pop neg 2 div 0 rmoveto        show    grestore} bind def% ------------------------------------------------------------%%Page: 1 1gsave%HeadingFONTNAME findfont FS 2 mul scalefont setfontXM 2 div YM FS 2.5 mul sub movetoHEADING Cshow20 30 translate/Scale 410 defScale dup scale/FS FS Scale div defFONTNAME findfont FS scalefont setfont%Minor gridlines.5 1 1 sethsbcolor.125 Scale div setlinewidth[1 Scale div 0.5 Scale div] 0 setdashylo yd ydd mul yhi{    xlo exch moveto    xr    0 rlineto stroke} forxlo xd xdd mul xhi{    ylo moveto    0 yr rlineto stroke} for%Major gridlines.5 1 1 sethsbcolor.25 Scale div setlinewidth[] 0 setdashylo yd yhi{    xlo exch moveto    xr 0 rlineto stroke} forxlo xd xhi{    ylo moveto    0 yr rlineto stroke} for%Draw axes.5 1 .75 sethsbcolor1.5 Scale div setlinewidthxlo ya exch movetoxr 0 rlineto strokexa ylo moveto0 yr rlineto stroke%Label axes0 0 0 sethsbcolor1 Scale div setlinewidthylo yd yhi{    dup ya ne    {        dup  xa exch moveto        nstr cvs Cshow    }    {pop} ifelse} forxlo xd xhi{    dup  ya FS sub moveto    nstr cvs Cshow} for%Plot the function1 1 1 sethsbcolor0 setlinewidthxmin dup Func movetoxmin dd xhi{    dup Func lineto} forstroke% ------------------------------------------------------------%Plot the tangential circles0.667 1 1 sethsbcolor%Draw a circle centred at (x,y), radius r. x y rad circle -/circle{    0 360 arc closepath    stroke    %fill}bind def/Circles [    [0.3277256800594015479201681 0.3277256800594015479201681]   %  0    [0.8472403783571132706458071 0.2058852404383162982761714]   %  1    [1.196330446963572442174227 0.1479754883597072063667725]    %  2    [1.457170563570700801711944 0.1149473591636858566230761]    %  3    [1.664835947360316196092632 0.09379274116919483875177791]   %  4    [1.837149719479212238679255 0.07914268122380788085162527]   %  5    [1.98432037353873873565022 0.06841820709567157326789252]    %  6    [2.112715021722272888532743 0.06023683746609180326843044]   %  7    [2.226563759351798027147458 0.05379405528690268192200967]   %  8    [2.328816545199463695987219 0.04859102068920534007800753]   %  9    [2.421610976707099981059273 0.04430245751525405579959111]   % 10    [2.506544800062194965998467 0.04070741644089758179177863]   % 11    [2.584843224433859386686089 0.03765065309405124930656815]   % 12    [2.657466190539199497615533 0.03501994502434459954306204]   % 13    [2.725179680938430811446842 0.03273218146729944830740853]   % 14    [2.788604608413581637742951 0.0307245136506329127257987]    % 15    [2.848251231979223300526761 0.02894854368759122521940847]   % 16    [2.904543948855239331093625 0.02736640232649798286569755]   % 17    [2.957839517825898172128305 0.02594803692149891150956139]   % 18    [3.008440695548979552671605 0.02466929574199710790796768]   % 19    [3.056606603892943516037283 0.023510548809969037001056]     % 20    [3.102560725013976407758698 0.02245567792861470103500921]   % 21    [3.14649714664160338621944 0.02149132561904016575462995]    % 22    [3.188585497582928526331931 0.02060632876213500235297651]   % 23    [3.228974889629759259389154 0.01979128607457459471098882]   % 24    [3.267797096492491684600178 0.01903822394378158744526435]   % 25    [3.305169140287560468314139 0.01834033549485494769541259]   % 26    [3.341195413255689629060282 0.01769177483610174848204746]   % 27    [3.375969431412557183170552 0.01708749334050138341731993]   % 28    [3.409575294155477738800599 0.01652310827854400557868039]   % 29    [3.442088907050643721055641 0.01599479658541971657700201]   % 30    [3.473579012445194570967779 0.01549920832791102732477801]   % 31    [3.50410806303164068489922 0.01503339573853258904822227]    % 32    [3.533732966224713869575652 0.01459475464597567669003092]   % 33] defCircles{    aload pop   %x rad    dup circle}forallgrestoreshowpage%%Trailerend%%EOF`

### Re: Fitting circles under a curve

Posted: Mon Jun 04, 2012 7:44 pm UTC
PM 2Ring wrote:Convergence is slow in both the original version and in your square version because for large n each circle (or square) is roughly the same size as its neighbours, which is a consequence of the fact that the slope of e-x soon becomes rather close to zero.

It's not easy to get accurate sums of such series: rounding errors soon swamp the true value, unless you're using a high precision math package.
Yeah, the radii (or side lengths) go roughly as 1/n, so the series is also converging as 1/n; at some point it becomes more accurate to estimate the sum of the tail using an approximation like 1/a'-1/a=2 (or the analog for squares).

### Re: Fitting circles under a curve

Posted: Thu Jun 07, 2012 12:31 pm UTC
Here are some figures I just calculated, going to 500,000 circles, using mpmath with 30 digits of precision.
The 500,000th circle has centre
(13.1223638684195789978373104073, 0.00000099999950898387034629469059663)

It intersects the curve at
(13.1223638684215789958732403709, 0.00000199999901796574069553548652458)

Its area is 3.14158956844521923817461696685e-12,
(The square of its radius is 9.99999017967981789428961297609e-13)

The cumulative area of the first 500,000 circles is
0.743661999490834727223258657868

Estimating the area of the the circles in the tail by pretending that those subsequent circles occupy pi/4 of the total area under the curve to the right of the current circle:

Full Area estimate:
0.74366357028481944(3)

EDIT

Here's an improved estimate, calculated using mpmath's Richardson extrapolation function on the full area estimate sequence to 600 circles (and 700 digits of precision)
0.
74366 35702 84819 44300 99238 75775 03206 43534 29249 46974 72191 92074 35985 79051 73238 65219 27019 13876 55412 89094 48770 15704 77939 49705 90801 42303 72590 83471 81663 20040 47347 81738 54206 64755 34534 67803 55961 87022 17665 47277 02235 44404 08261 28457 29662 84420 21838 76746 95031 83359 28996 16532 48554 92338 71017 90695 42014 51346 24045 03704 25283 74185 81212 39655 41034 90162 29032 20964 87179 94217 07619 93924 61236 26406 76319 77600

More of the generated digits are probably correct, but that seemed like a nice stopping point.

### Re: Fitting circles under a curve

Posted: Mon Jun 11, 2012 2:09 am UTC
nadando wrote:Is there a closed form expression for the same scenario but with squares instead of circles? It's much easier to derive the equation (a(0) = 0, a(n) = W(e^(a(n - 1))) + a(n - 1)) but the sum seems to converge very slowly (maybe my implementation of the lambert W function is just inefficient). I get something around 0.824.

There might be a closed form expression for the square area, but the Inverse Symbolic Calculator doesn't find anything.

Using Richardson approximation, I get 0.8242221990147699488606, but this series extrapolates much more slowly than the circle series, and I had to use 5000 squares and 3000 digits precision to get that result.