Fitting circles under a curve

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Randommelon
Posts: 5
Joined: Mon May 28, 2012 10:56 am UTC

Fitting circles under a curve

Postby Randommelon » 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.

User avatar
Heptadecagon
Posts: 36
Joined: Mon May 28, 2012 7:11 pm UTC

Re: Fitting circles under a curve

Postby Heptadecagon » 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...

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

Re: Fitting circles under a curve

Postby Timefly » 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.

Randommelon
Posts: 5
Joined: Mon May 28, 2012 10:56 am UTC

Re: Fitting circles under a curve

Postby Randommelon » 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.

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fitting circles under a curve

Postby eta oin shrdlu » 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.

Ben-oni
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Fitting circles under a curve

Postby Ben-oni » 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.

Randommelon
Posts: 5
Joined: Mon May 28, 2012 10:56 am UTC

Re: Fitting circles under a curve

Postby Randommelon » 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.

User avatar
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

Postby jestingrabbit » 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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Ben-oni
Posts: 278
Joined: Mon Sep 26, 2011 4:56 am UTC

Re: Fitting circles under a curve

Postby Ben-oni » 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.

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

Re: Fitting circles under a curve

Postby Timefly » 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.

Randommelon
Posts: 5
Joined: Mon May 28, 2012 10:56 am UTC

Re: Fitting circles under a curve

Postby Randommelon » 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.
Last edited by Randommelon on Wed May 30, 2012 9:15 am UTC, edited 1 time in total.

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fitting circles under a curve

Postby eta oin shrdlu » 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.

Randommelon
Posts: 5
Joined: Mon May 28, 2012 10:56 am UTC

Re: Fitting circles under a curve

Postby Randommelon » 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).

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fitting circles under a curve

Postby eta oin shrdlu » 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.]

nadando
Posts: 33
Joined: Wed Apr 21, 2010 8:33 pm UTC

Re: Fitting circles under a curve

Postby nadando » 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.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Fitting circles under a curve

Postby PM 2Ring » 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 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
%/Palatino-Roman
/Times-Roman
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

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fitting circles under a curve

Postby eta oin shrdlu » 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).

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Fitting circles under a curve

Postby PM 2Ring » 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. :)

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Fitting circles under a curve

Postby PM 2Ring » 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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 2 guests