SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

circle covering

March 8th, 2006, 2:36 pm

QuoteOriginally posted by: beatlemaniaQuoteOriginally posted by: mattcushmanIf we can find a non-negative function f(x,y) such that the integral of f(x,y) over any strip intersected with the circle is equal to A, while f(x,y) integrated over the whole circle is B with B > 9A, we are done.Can you tell me why is that?Integral calculus. If the 9 strips covered the circle you would have that the integral of f over the circle is equal to the integral of f over the union of the strips. Since f is non-negative, this is less than the sum over the 9 strips, of the integral of f over that strip. Think of f as defining a measure mu on the disk, then mu(S_1 union ... union S_9) <= mu(S_1) + ... + mu(S_9)
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 19th, 2006, 10:29 am

QuoteOriginally posted by: sevvostThis is the Tarski's Plank Problem. The "ingenious argument of Bang" Mathworld refers to is AFAIK essentially the same as the solution given in this thread by mattcushman. Except it is formulated in geometric terms - he builds a sphere with the given circle as its equator and operates with the areas of spheric strips that are projections of the strips on the circle.Having found the planks I now want to circle pack each plank. But a packed circle must be inside the big one. If not we have to pack the left-over region with smaller and smaller circles. Is this a good approach to circle packing?
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 19th, 2006, 10:33 am

CirclePAckingAnyone know this book?
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
wannabequantie
Posts: 70
Joined: October 30th, 2004, 12:13 pm

circle covering

March 23rd, 2006, 2:06 pm

Yes i know about this book, though i don't think this is the stuff you're looking for. Circle packing is really the study of discrete conformal mappings. You can prove analogues of theorems from complex analysis, like schwarz lemma, riemann mapping theorem etc. This is very different from sphere packings which seems to be more like what you're after? If you want to read more about circle packings check out ken stephenson page http://www.math.utk.edu/~kens/ . He has lots of very nice papers you can download. Hope that helps.
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 23rd, 2006, 6:03 pm

QuoteOriginally posted by: wannabequantieYes i know about this book, though i don't think this is the stuff you're looking for. Circle packing is really the study of discrete conformal mappings. You can prove analogues of theorems from complex analysis, like schwarz lemma, riemann mapping theorem etc. This is very different from sphere packings which seems to be more like what you're after? If you want to read more about circle packings check out ken stephenson page http://www.math.utk.edu/~kens/ . He has lots of very nice papers you can download. Hope that helps.Actually, believe it or not I want to pack circles The application is not QF-related at all. The good examples I want to do are on pages 5 and 77.I reckon however that some of the maths could be used in QF (complex numbers).Thanks for tip on the articles.
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl
 
User avatar
sevvost
Posts: 361
Joined: February 17th, 2006, 7:47 pm

circle covering

March 23rd, 2006, 7:02 pm

I wonder if you had a chance to take a look at the Fejes Tóth book mentioned earlier. I am not sure what is the problem you are trying to solve, so I don't know if his stuff is exactly relevant, but I think the book is a real pleasure to read. He devotes a considerable number of pages to precise estimations of circle packings for convex shapes - both same and different size circles. If that could be any help, I can quote some of his results.
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 31st, 2006, 7:31 pm

QuoteOriginally posted by: sevvostI wonder if you had a chance to take a look at the Fejes Tóth book mentioned earlier. I am not sure what is the problem you are trying to solve, so I don't know if his stuff is exactly relevant, but I think the book is a real pleasure to read. He devotes a considerable number of pages to precise estimations of circle packings for convex shapes - both same and different size circles. If that could be any help, I can quote some of his results.Managed to get the 1953 edition of the book. Amazing stuff.His circle packing might not be exactly what we need because I am not sure what happens at the edges of the bounding convex shape. The anti-aliasing effects might be too disruptive. A possibility is to fill in near the edges with smaller and smaller circles.The discete conformal mapping technique looks promising even though it is for circles. Of course, it is a good start.The general problem is to pack arbitrary shapes into an abritrary convex outer shape with packing as 'dense' as possible.Thanks for the reference.
Last edited by Cuchulainn on March 30th, 2006, 10:00 pm, edited 1 time in total.
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On