SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
prospero
Posts: 47
Joined: March 16th, 2002, 4:00 am

circle covering

April 25th, 2005, 9:03 pm

I start assuming that the covering exists, and then from that covering I pick only a strip covering the centre.Thenfor each for the points chosen in 2) I find the strip that maximize the piece of the circumference covered- those strips may not be in the original covering.The eight strips turn out to be parallel to each other and nonoverlaping, so none of the stripscan cover more than one point.
 
User avatar
Aaron
Posts: 6433
Joined: July 23rd, 2001, 3:46 pm

circle covering

April 26th, 2005, 2:06 pm

Okay, so you've shown that the maximum circumference that can be covered by the strips that cover the eight points is less than the the total circumference of the circle minus the maximum circumference that can be covered by the strip that goes through the center.But I think you haven't shown that you need eight separate strips to cover the eight points. If you use fewer than eight strips you cover less of the circumference, that's true, but you have some extra strips to place that could make up the difference.I don't think you need the eight points. I don't think you can place nine strips to cover the circumference of the circle, if one of the strips must also cover the center.
 
User avatar
Mandark
Posts: 12
Joined: January 11th, 2005, 2:33 pm

circle covering

April 26th, 2005, 3:01 pm

Aaron, can't a strip with its outer edge just touching the circle cover 2*acos(.8) = 1.287 radians > 2pi/5 meaning that you can cover the circumference with only 5 strips. Also, I agree that prospero's proof is incomplete. He presupposes constraints on the optimal solution that are not obviously true.
 
User avatar
Aaron
Posts: 6433
Joined: July 23rd, 2001, 3:46 pm

circle covering

April 26th, 2005, 3:09 pm

You're right, I miscalculated. Back to the drawing board. I think prospero has the right idea. There is a maximum circumference that a strip covering the center of the circle can cover. We also need to cover a point in the interior 1 meter away from the center, there is a maximum circumference that that strip can cover. Now we need to identify a third point in the interior that is not covered by either of the first two strips, and continue in that manner.
 
User avatar
leherbert
Posts: 39
Joined: February 20th, 2005, 5:18 pm

circle covering

April 28th, 2005, 2:07 pm

What about trying by covering one of the largest square inscribed in that circle first, and showing the rest cannot be coverred with the rest of the stripes?
Last edited by leherbert on April 27th, 2005, 10:00 pm, edited 1 time in total.
 
User avatar
mattcushman
Posts: 100
Joined: July 14th, 2002, 3:00 am

circle covering

April 28th, 2005, 5:36 pm

I tried a bunch of solutions along those lines, playing with both arc length and area. The solution I gave below is in a way inspired by those, but I needed to use this funny area w.r.t a different measure to get it to work.
 
User avatar
seluraved
Posts: 3
Joined: March 3rd, 2005, 7:14 pm

circle covering

May 2nd, 2005, 10:08 pm

I thought of the problem in a slightly different context: Assume a covering exists and place the first segment on the circle. Consider the line C that bisects the segment into two 1/2 pieces(this will be a chord on the circle). There exists a segment D of length 10 units that bisects C(perpendicular) that goes through the center of the circle. At most 1 unit of this line will be covered by the segment. Therefore we have a type of pigeonhole argument with 9 or more units and 8 segments and we're done. If you orient the 2nd segment such that it covers D then you can just use the same logic to show that the segment perpendicular to line that bisects the 2nd segment will not be covered...don't know whether this suffices however it may give more insight.
 
User avatar
sevvost
Posts: 361
Joined: February 17th, 2006, 7:47 pm

circle covering

February 27th, 2006, 5:56 am

This 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.
 
User avatar
beatlemania
Posts: 3
Joined: April 22nd, 2004, 6:24 pm

circle covering

March 4th, 2006, 3:15 am

QuoteOriginally 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?
Last edited by beatlemania on March 3rd, 2006, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 5th, 2006, 3:10 pm

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.HiOn a somewhat related problem that a friend of mine is working on is "Circle packing problems", i.e. packing circles as close as possible into a closed 2d shape.Know any good books?Once we can do circles. It might be worth trying other shapes like hexagons.
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 5th, 2006, 8:37 pm

I know an excellent book by László Fejes Tóth that covers the subject extensively: Fejes T'oth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum, zweite Auflage, Springer Verlag, 1972.Unfortunately I do not know if it ever was translated into English. I heard of a Russian translation - not sure if that helps, either
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 6th, 2006, 3:47 pm

QuoteOriginally posted by: sevvostI know an excellent book by László Fejes Tóth that covers the subject extensively: Fejes T'oth, L.: Lagerungen in der Ebene, auf der Kugel und im Raum, zweite Auflage, Springer Verlag, 1972.Unfortunately I do not know if it ever was translated into English. I heard of a Russian translation - not sure if that helps, either Thanks, will try to locate it at the local uni.BTW have you worked in this area?
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 6th, 2006, 6:37 pm

QuoteOriginally posted by: CuchulainnBTW have you worked in this area?No, not really. Just dabbled a little bit at high school...
 
User avatar
sevvost
Posts: 361
Joined: February 17th, 2006, 7:47 pm

circle covering

March 6th, 2006, 10:07 pm

BTW, I suppose you have already visited the Mathworld's Circle Packing page, haven't you? It has a lot of references.
 
User avatar
Cuchulainn
Posts: 63379
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

circle covering

March 7th, 2006, 8:29 am

QuoteOriginally posted by: sevvostBTW, I suppose you have already visited the Mathworld's Circle Packing page, haven't you? It has a lot of references.Thanks again, I was not aware of this.We are considering writing one in C++ from because it has to be integrated into something else. It is one issue knowing what the algorithm is and a second issue knowing if it is a lot of lines of code to do the packing. In principle, arbitrary shapes need to be included eventually.
Last edited by Cuchulainn on March 6th, 2006, 11: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