[R] circle fill problem
Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] circle fill problem
Mini This is a hard problem in general. Recreational mathematics has wrestled with this and similar problems over the years; the general field is the set cover problem but in your case the sets are uncountably infinite (and there are uncountably many of them). I would be surprised if your problem were not NP complete. HTH Robin On 8 Feb 2007, at 05:15, MINI GHOSH wrote: Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] circle fill problem
Robin Mini, For those interested, googling for the 'orange packing problem' as it is known, or more officially the sphere packing problems gives you quite a few hits on these and similar problems. So at least the 3-d case the problem has been solved (I imagine the problem is easier in 2-d ...) hth, Ingmar On 8 Feb 2007, at 09:52, Robin Hankin wrote: Mini This is a hard problem in general. Recreational mathematics has wrestled with this and similar problems over the years; the general field is the set cover problem but in your case the sets are uncountably infinite (and there are uncountably many of them). I would be surprised if your problem were not NP complete. HTH Robin On 8 Feb 2007, at 05:15, MINI GHOSH wrote: Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] circle fill problem
Dear Ingmar and Robin, Thanks for you suggestions. I will see to it. Regards, Mini --- Ingmar Visser [EMAIL PROTECTED] wrote: Robin Mini, For those interested, googling for the 'orange packing problem' as it is known, or more officially the sphere packing problems gives you quite a few hits on these and similar problems. So at least the 3-d case the problem has been solved (I imagine the problem is easier in 2-d ...) hth, Ingmar On 8 Feb 2007, at 09:52, Robin Hankin wrote: Mini This is a hard problem in general. Recreational mathematics has wrestled with this and similar problems over the years; the general field is the set cover problem but in your case the sets are uncountably infinite (and there are uncountably many of them). I would be surprised if your problem were not NP complete. HTH Robin On 8 Feb 2007, at 05:15, MINI GHOSH wrote: Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] circle fill problem
Hello Ingmar In Kepler's sphere packing problem the spheres are not allowed to overlap, which would suggest to me that different tactics should perhaps be used. Mini's problem is formally a cover problem, and the sphere packing problem is a packing problem. The two are related, but tend not to have direct relevance to one another. Also be aware that Kepler's conjecture refers to the packing fraction limit as the space available tends to infinity. My understanding is that Kepler's conjecture has now been proved beyond all reasonable doubt, but how to use this in Mini's problem is not clear to me. rksh On 8 Feb 2007, at 09:21, Ingmar Visser wrote: Robin Mini, For those interested, googling for the 'orange packing problem' as it is known, or more officially the sphere packing problems gives you quite a few hits on these and similar problems. So at least the 3-d case the problem has been solved (I imagine the problem is easier in 2-d ...) hth, Ingmar On 8 Feb 2007, at 09:52, Robin Hankin wrote: Mini This is a hard problem in general. Recreational mathematics has wrestled with this and similar problems over the years; the general field is the set cover problem but in your case the sets are uncountably infinite (and there are uncountably many of them). I would be surprised if your problem were not NP complete. HTH Robin On 8 Feb 2007, at 05:15, MINI GHOSH wrote: Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
Re: [R] circle fill problem
I suspect the number is: trunc((x + 3*r)/(2*r)) * trunc((y + 3*r)/(2*r)) + trunc((x + 2*r)/(2*r)) * trunc((y + 2*r)/(2*r)) where x and y are the dimensions of the rectangle and r is the radius of the circle. I have some code which graphs the overlapping circles if you want visually to check the algorithm (but although it is only a page, I won't post it here). HTH Ray Brownrigg On Thursday 08 February 2007 22:39, MINI GHOSH wrote: Dear Ingmar and Robin, Thanks for you suggestions. I will see to it. Regards, Mini --- Ingmar Visser [EMAIL PROTECTED] wrote: Robin Mini, For those interested, googling for the 'orange packing problem' as it is known, or more officially the sphere packing problems gives you quite a few hits on these and similar problems. So at least the 3-d case the problem has been solved (I imagine the problem is easier in 2-d ...) hth, Ingmar On 8 Feb 2007, at 09:52, Robin Hankin wrote: Mini This is a hard problem in general. Recreational mathematics has wrestled with this and similar problems over the years; the general field is the set cover problem but in your case the sets are uncountably infinite (and there are uncountably many of them). I would be surprised if your problem were not NP complete. HTH Robin On 8 Feb 2007, at 05:15, MINI GHOSH wrote: Dear R user, I want to know is there a way to find the minimum number of circles (of given radius) required to fill a given area (say rectangular) where overlapping of circles is allowed. Thanks, Regards, Mini Ghosh __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. -- Robin Hankin Uncertainty Analyst National Oceanography Centre, Southampton European Way, Southampton SO14 3ZH, UK tel 023-8059-7743 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting- guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
