SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

### circle covering

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)

Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### circle covering

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

Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### circle covering

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

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

wannabequantie
Posts: 70
Joined: October 30th, 2004, 12:13 pm

### circle covering

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.

Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### circle covering

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

sevvost
Posts: 361
Joined: February 17th, 2006, 7:47 pm

### circle covering

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.

Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### circle covering

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

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

 JOBS BOARD

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

GZIP: On