Fitting circles under a curve
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 5
 Joined: Mon May 28, 2012 10:56 am UTC
Fitting circles under a curve
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 yaxis, the xaxis 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 xaxis. 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 xvalue of the point at which the first circle touches the curve involves working out an x such that xsqrt((1+e^(2x))x^(2))+sqrt(2xe^(3x))e^(x)=0, which is a transcendental equation.
Thanks.
I suspect that the answer will be pretty complicated. Just working out the xvalue of the point at which the first circle touches the curve involves working out an x such that xsqrt((1+e^(2x))x^(2))+sqrt(2xe^(3x))e^(x)=0, which is a transcendental equation.
Thanks.
 Heptadecagon
 Posts: 36
 Joined: Mon May 28, 2012 7:11 pm UTC
Re: Fitting circles under a curve
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
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 (xa)^3 + (xa)^2 + (xa)  a^2 = 0 where a is the x coordinate of the centre of the circle.

 Posts: 5
 Joined: Mon May 28, 2012 10:56 am UTC
Re: Fitting circles under a curve
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=(xr)^2+(yr)^2, which can be rearranged to give y=r+sqrt(2rxx^2). We equate the value at the point of intersection for both equations and the derivative at that point, to give equations e^(x)=(xr)/sqrt(2xrx^2) as well as r^2=(e^(x)r)^2+(xr)^2, which can be manipulated to give xsqrt(x^2(e^(2x)+1))=e^xsqrt(2xe^(3x)). Wolfram alpha gives approximately x=0.498 and r=0.328. x and r don't seem to satisfy the relation (xr)^3 + (xr)^2 + (xr)  r^2 = 0.
The cirle has radius r, and has been shifted r right and r up. We have r^2=(xr)^2+(yr)^2, which can be rearranged to give y=r+sqrt(2rxx^2). We equate the value at the point of intersection for both equations and the derivative at that point, to give equations e^(x)=(xr)/sqrt(2xrx^2) as well as r^2=(e^(x)r)^2+(xr)^2, which can be manipulated to give xsqrt(x^2(e^(2x)+1))=e^xsqrt(2xe^(3x)). Wolfram alpha gives approximately x=0.498 and r=0.328. x and r don't seem to satisfy the relation (xr)^3 + (xr)^2 + (xr)  r^2 = 0.
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fitting circles under a curve
I think it should be
0 = (xa)^{3}+2(xa)^{2}+(xa)a^{2}(xa)2a^{2}.
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.
0 = (xa)^{3}+2(xa)^{2}+(xa)a^{2}(xa)2a^{2}.
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
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.

 Posts: 5
 Joined: Mon May 28, 2012 10:56 am UTC
Re: Fitting circles under a curve
Benoni 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.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Fitting circles under a curve
Yeah, they don't form a geometric progression. If they did, their centres would be on a straight line.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Fitting circles under a curve
Ah, right. It only scales in one direction. I guess I was mentally filling it in with ellipses.
Re: Fitting circles under a curve
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.

 Posts: 5
 Joined: Mon May 28, 2012 10:56 am UTC
Re: Fitting circles under a curve
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 = (xa)^3+2(xa)^2+(xa)a^2(xa)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.
Last edited by Randommelon on Wed May 30, 2012 9:15 am UTC, edited 1 time in total.
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fitting circles under a curve
If a_{n} is the radius of the nth circle, then for large n
(1/a_{n})  (1/a_{n1}) ≈ 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.
(1/a_{n})  (1/a_{n1}) ≈ 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.

 Posts: 5
 Joined: Mon May 28, 2012 10:56 am UTC
Re: Fitting circles under a curve
eta oin shrdlu wrote:If a_{n} is the radius of the nth circle, then for large n
(1/a_{n})  (1/a_{n1}) ≈ 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).
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fitting circles under a curve
Here's an informal argument.Randommelon wrote:eta oin shrdlu wrote:If a_{n} is the radius of the nth circle, then for large n
(1/a_{n})  (1/a_{n1}) ≈ 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?
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^{x2a}≈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(y^{k}) 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 = (xu)^{2} + y^{2}  2ay [circle touches curve]
0 = (xu) + ay  y^{2} [circle tangent to curve]
4a_{0}a = (uu_{0})^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 (u_{0},a_{0}) with radius a_{0}. [You can solve the second and third equations for a to get your equation for radius.]
Re: Fitting circles under a curve
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
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
%!PSAdobe3.0
%%BoundingBox: 0 0 1500 500
%%Title: (Exponential Circles)
%%Creator: (PM 2Ring)
%%Creationdate: (19:43:00 June 4 2012)
%%Pages: 1
%%EndComments
%With fine subdivisions
24 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
%/PalatinoRoman
/TimesRoman
def
/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 1
gsave
%Heading
FONTNAME findfont FS 2 mul scalefont setfont
XM 2 div YM FS 2.5 mul sub moveto
HEADING Cshow
20 30 translate
/Scale 410 def
Scale dup scale
/FS FS Scale div def
FONTNAME findfont FS scalefont setfont
%Minor gridlines
.5 1 1 sethsbcolor
.125 Scale div setlinewidth
[1 Scale div 0.5 Scale div] 0 setdash
ylo yd ydd mul yhi
{
xlo exch moveto
xr
0 rlineto stroke
} for
xlo xd xdd mul xhi
{
ylo moveto
0 yr rlineto stroke
} for
%Major gridlines
.5 1 1 sethsbcolor
.25 Scale div setlinewidth
[] 0 setdash
ylo yd yhi
{
xlo exch moveto
xr 0 rlineto stroke
} for
xlo xd xhi
{
ylo moveto
0 yr rlineto stroke
} for
%Draw axes
.5 1 .75 sethsbcolor
1.5 Scale div setlinewidth
xlo ya exch moveto
xr 0 rlineto stroke
xa ylo moveto
0 yr rlineto stroke
%Label axes
0 0 0 sethsbcolor
1 Scale div setlinewidth
ylo yd yhi
{
dup ya ne
{
dup xa exch moveto
nstr cvs Cshow
}
{pop} ifelse
} for
xlo xd xhi
{
dup ya FS sub moveto
nstr cvs Cshow
} for
%Plot the function
1 1 1 sethsbcolor
0 setlinewidth
xmin dup Func moveto
xmin dd xhi
{
dup Func lineto
} for
stroke
% 
%Plot the tangential circles
0.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
] def
Circles
{
aload pop %x rad
dup circle
}forall
grestore
showpage
%%Trailer
end
%%EOF
 eta oin shrdlu
 Posts: 451
 Joined: Sat Jan 19, 2008 4:25 am UTC
Re: Fitting circles under a curve
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).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.
Re: Fitting circles under a curve
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.14158956844521923817461696685e12,
(The square of its radius is 9.99999017967981789428961297609e13)
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.
The 500,000th circle has centre
(13.1223638684195789978373104073, 0.00000099999950898387034629469059663)
It intersects the curve at
(13.1223638684215789958732403709, 0.00000199999901796574069553548652458)
Its area is 3.14158956844521923817461696685e12,
(The square of its radius is 9.99999017967981789428961297609e13)
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
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.
Who is online
Users browsing this forum: No registered users and 12 guests