Author 
Topic: Maximum Coverage by Discs (Read 2685 times) 

Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Maximum Coverage by Discs
« on: Dec 4^{th}, 2003, 6:26am » 
Quote Modify

A problem related to pjay's coins covering a table question: What is the area of the largest region with a simplyconnected interior that can be completely covered by N discs of radius 1? Because of the simplyconnected requirement, the discs will have to overlap. So the answer is < N[pi]. But how much less? (The originally stated problem is trivial. Below are two far more interesting versions.) What is the area of the largest convex region that can be completely covered by N discs of radius 1? What is the largest possible area of the convex hull of the centers of the discs, if the discs completely cover the convex hull? (I don't know the answer.)

« Last Edit: Dec 5^{th}, 2003, 9:50am by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Dudidu
Full Member
Posts: 227


Re: Maximum Coverage by Discs
« Reply #1 on: Dec 4^{th}, 2003, 7:01am » 
Quote Modify

on Dec 4^{th}, 2003, 6:26am, Icarus wrote:What is the area of the largest region with a simplyconnected interior that can be completely covered by N discs of radius 1? 
 I just want to be sure: [smiley=spot.gif] What do you mean by "simplyconnected interior" ? (i.e. do you mean that [forall] two points (in some circles), [exists] a path between them that passes in the interiors of circles ?)


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Maximum Coverage by Discs
« Reply #2 on: Dec 4^{th}, 2003, 8:03am » 
Quote Modify

on Dec 4^{th}, 2003, 7:01am, Dudidu wrote: I just want to be sure: [smiley=spot.gif] What do you mean by "simplyconnected interior" ? (i.e. do you mean that [forall] two points (in some circles), [exists] a path between them that passes in the interiors of circles ?) 
 I'm a little rusty, but my recollection is that a region is simply connected if there is no partition of the region into two subregions, A,B, so that there is an [epsilon]>0 such that [forall]points a[in]A, the open ball of radius epsilon around a does not intersect B. Your definition is for pathconnectedness. I believe that the answer to the question is: :: The target area can be made arbitrarily close to N*pi by considering the silhouette of a string of barely overlapping coins (and reducing the "barely" as small as you like) ::


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #3 on: Dec 4^{th}, 2003, 8:13am » 
Quote Modify

How about when we take the area inside the convex hull of the set of disc centers.. You can't get anywhere near N[pi] then

« Last Edit: Dec 4^{th}, 2003, 8:15am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Maximum Coverage by Discs
« Reply #4 on: Dec 4^{th}, 2003, 9:08am » 
Quote Modify

That also neatly sidesteps the question of connectedness... I think that considering general convex regions is possibly better still, though for arbitrarily large N, it probably comes to much the same thing.


IP Logged 



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #5 on: Dec 4^{th}, 2003, 11:14am » 
Quote Modify

Quote:though for arbitrarily large N, it probably comes to much the same thing 
 I'm not sure what you mean by this, but i agree with towr in that you won't get anywhere near n\pi. by the way, can anybody tell me how to insert latex typesetted symbols?


IP Logged 



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #6 on: Dec 4^{th}, 2003, 11:21am » 
Quote Modify

ahhhh, i see. towr is suggesting maximizing the part of the convex hull of the interior of n circles which is contained in the interior of the circles, where as rms is suggesting that we take an arbitrary convex shape and see what the smallest n is that covers it. well in that case, i think towr's suggestion is the way to go. the reason is that n would depend heavily on the shape. in general it is not true that Quote:though for arbitrarily large N, it probably comes to much the same thing 
 since we can take an arbitrarily long line segment which takes n circles to cover, but has no area. on the otherhand the convexhull of the interior intersected with the interior of n circles is of order n.


IP Logged 



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #7 on: Dec 4^{th}, 2003, 11:31am » 
Quote Modify

i don't have a proof of this (i'll try to work on one), but for large n i think the answer is given by the following algorithm: inscribe a regular hexagon into the circles then tile a plane with the hexagons in such a way to maximize the convex hull, the boundary poses a problem...


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Maximum Coverage by Discs
« Reply #8 on: Dec 4^{th}, 2003, 5:27pm » 
Quote Modify

SimplyConnected = pathconnected (any two points can be connected by a curve lying inside the set) + every loop (continuous closed curve) inside the set can be contracted down to a point while staying inside. For instance, the plane is simplyconnected, but the punctured plane (1 point removed) is not, because a circle around the puncture cannot be contracted to a point without passing through the puncture. Also, the sphere is simplyconnected, but the torus is not. A few minutes after posting this, I realized that the solution rmsgrey has given does indeed allow you to reach any value less than N[pi], which was not what I wanted at all. Unfortunately I did not have time to come back and correct the problem. I was intending to change it to "convex", like rmsgrey has suggested, but the convex hull question is also interesting, and perhaps easier to answer. So I'm changing the original problem to cover both. on Dec 4^{th}, 2003, 11:14am, pjay wrote:by the way, can anybody tell me how to insert latex typesetted symbols? 
 We don't have latex style typesetting, or even full HTML formatting capabilities (there are security issues with that). Instead you can use a set of tags, placed in [ ], which YaBB supplies. Most are available in the buttons over the reply window. William has supplemented YaBB's default tags with some of his own. [hide] hidden text [/hide] allows you to hide text, so that someone reading the thread has a chance to think on the problem him or her self before seeing your answer. A couple months ago, William also added the math symbolry we've been using. If you look to the left of the reply window, you will see a box containing symbols. You can place them by clicking on the image, or by adding in the code manually (which is what I usually do for such things as [pi], which is given by the code [pi]). If you click on the "View All Symbols" link, it will open popup window with all the symbols available, rather than the abbreviated list in the box. However, those symbols do not have shortcut codes, and must be entered in as [smiley=symbolname.gif]. These symbols are implemented as "smileys"  pictures imbedded in the text. Unfortunately, this limits their utility, but this is still a vast improvement over how things were before William worked his magic. If you have something too complicated to be expressed with them, then you can avail yourself of towr's formula generator. Just find any of his posts (they are everywhere  you can't miss them ) and click on the link in his signature. After you have produced your formula, use the [ img ] tag (4th from the left on the bottom row of buttons) to link to it in your post  or you can use the attachment tool to copy it to the forum directory, so that it will be visible even if towr's site is incommunicado.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #9 on: Dec 5^{th}, 2003, 12:49am » 
Quote Modify

So if I understand it a large x would be simply connected? Quote:What is the largest possible area of the convex hull of the centers of the discs, if they completely cover a simplyconnected region? 
 This isn't really what I intended, and it isn't too hard. Since you can f.i. just make a large x out of coins. Only the simply connected region has to be covered here, so you get a lot of uncovered area added to your answer. For an x shape the total area would be (just short of) 1/2 (N1)^{2} (for odd N). With a triangular shape I get 3[sqrt]3 ((N  1)/3)^{2} (for N=3k+1 for some integer k) I think this is also the maximum.. I had intended for the convex area to also be covered, and so it would be a slightly smaller area than rmsgrey's case, but otherwise similar (though slightly easier to find, I think)

« Last Edit: Dec 5^{th}, 2003, 1:06am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Maximum Coverage by Discs
« Reply #10 on: Dec 5^{th}, 2003, 9:49am » 
Quote Modify

Yes, an x is simply connected. A planar region is simply connected if it has no holes in it. I.e. if you draw a simple closed curve within it, everything inside the curve is also inside the region. And yes, I didn't state it properly yet again!


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



rmsgrey
Uberpuzzler
Gender:
Posts: 2844


Re: Maximum Coverage by Discs
« Reply #11 on: Dec 5^{th}, 2003, 5:53pm » 
Quote Modify

I'm sorry, my definition is of connectedness, not simple connectedness... it's been a while since I did topology properly


IP Logged 



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #12 on: Dec 6^{th}, 2003, 11:27am » 
Quote Modify

[quote author=towr link=board=riddles_hard;num=1070547965;start=0#9 date=12/05/03 at 00:49:29] With a triangular shape I get 3[sqrt]3 ((N  1)/3)^{2} (for N=3k+1 for some integer k) I think this is also the maximum.. quote] actually for large n you could draw a very large circle and remove one point. what's left is simply connected. cover it with a ring of circles that barely overlap at except at the removed point there the circles should not overlap. what's left is simply connected and its convex hull should maximize the misphrased question. comment: i'm enjoying this discussion because it highlights how important it is t phrase things correctly [not only in the sciences, but i'm told it is important in humanities as well, although the "science wars" would suggest otherwise... (google search under "sokal" if you are interested)]. This fact took me a long time to learn, and i am still daily relearning it...


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #13 on: Dec 7^{th}, 2003, 7:54am » 
Quote Modify

on Dec 6^{th}, 2003, 11:27am, pjay wrote:actually for large n you could draw a very large circle and remove one point. what's left is simply connected. cover it with a ring of circles that barely overlap at except at the removed point there the circles should not overlap. what's left is simply connected and its convex hull should maximize the misphrased question. 
 I don't think so The area you'd get would be about (2N/(2pi))^{2} * pi ~= 0.32 N^{2} which is rather smaller than about 0.57 (N1)^{2} Surrounding the area is a bad idea, since you can get much more area with a (triangular) skeleton.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Maximum Coverage by Discs
« Reply #14 on: Dec 7^{th}, 2003, 11:23am » 
Quote Modify

on Dec 6^{th}, 2003, 11:27am, pjay wrote:actually for large n you could draw a very large circle and remove one point. what's left is simply connected. 
 No  unless that point is on the boundary of the circle, it is not simply connected. Simplyconnected means that [pi]_{1}(X) = {0}. For the punctured disc, [pi]_{1} = [bbz].


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #15 on: Dec 7^{th}, 2003, 11:35am » 
Quote Modify

I think it's pretty evident that that's what he meant (though you can hardly be too precise around here) But being precise (betting on mathworld being right), "A circle is the set of points equidistant from a given point O."


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Maximum Coverage by Discs
« Reply #16 on: Dec 7^{th}, 2003, 11:40am » 
Quote Modify

A circle is not a disk A circle is not a disk A circle is not a disk ... How many times does it take to remember this? My apologies, pjay.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #17 on: Dec 7^{th}, 2003, 1:24pm » 
Quote Modify

ahh yes towr, you are correct. Anyone have a proof that the skeleton of a triangle (like the inside of a peace symbol) is the way to go if you want to get the most area when you take the convex hull of a simply connected one dimensional shape (maximize area per length) seems like quite a hard problem in itself.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #18 on: Dec 7^{th}, 2003, 3:23pm » 
Quote Modify

I don't think it can really qualify as one dimensional, since it can only lie in a two (or higher) dimensional plane.. (And otherwise it wouldn't contain an area) I think it comes down to getting a number of points as far apart as possible, and connecting them with the least total length of lines possible. And that is a problem that has allready been dealt with on this forum somewhere. All lines have to meet at 120 degree angles. That still leaves some possible configurations, but I think three boundary points maximizes it. At the very least I'd say the boundary points have to lay equidistant on a circle, since taking one of the points and laying it far from the rest will make the area grow approximatley linearly with it's distance, but you don't want the area to scale linearly with N, but quadraticly (or better, but clearly that's not possible). Proofing it is another thing though..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #19 on: Dec 7^{th}, 2003, 3:49pm » 
Quote Modify

on Dec 7^{th}, 2003, 3:23pm, towr wrote:I don't think it can really qualify as one dimensional, since it can only lie in a two (or higher) dimensional plane.. (And otherwise it wouldn't contain an area) I think it comes down to getting a number of points as far apart as possible, and connecting them with the least total length of lines possible. And that is a problem that has allready been dealt with on this forum somewhere. All lines have to meet at 120 degree angles. 
 well, in spirit it is one dimensional since we are considering large n. so the area covered by the discs is negligible. If we were to pursue the misphrased question then i guess the wording would be something like my last post. Just to clarify why I wrote the phrase "1dimensional" as far as intuition on the misphrased question, it seems to that the arguments must go much deeper. for instance, what is meant by getting a number of points as far apart as possible, and connecting them with the least total length? are we considering the sum of all distances between any two given points? Are we trying to optimize this over the number of points? I think the first thing to do is to fix the number of points we are planning to use. when we connect them we must remember that we need the resulting set to be simply connected. Also, where does the area of the convex hull come into all this? what relation does it have to the distances and number of points we are using? I have no clue as to how to even begin to prove that 120 degrees is the correct angle to use when trying to maximize the area of convex hulls...


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #20 on: Dec 8^{th}, 2003, 1:25am » 
Quote Modify

on Dec 7^{th}, 2003, 3:49pm, pjay wrote:well, in spirit it is one dimensional since we are considering large n. 
 I disagree, a circle can't exists on a line, so it can't be one dimensional (at least not in an euclidean space), it can only exist in two dimensions, and thus is two dimensional. Quote:as far as intuition on the misphrased question, it seems to that the arguments must go much deeper. for instance, what is meant by getting a number of points as far apart as possible, and connecting them with the least total length? 
 For the latter, imagine three cities, and connecting them with the least amount of road possible. As for the former, that's simply in terms of euclidean distance between the points. Quote:are we considering the sum of all distances between any two given points? Are we trying to optimize this over the number of points? 
 Both in a sense. We're trying to find the number of points such that we get the maximum area for the convex hull when the 'connective distance' (roadsystem) between the points is minimized. Quote:I think the first thing to do is to fix the number of points we are planning to use. 
 Not if you want to find the number N which is optimal. Quote:when we connect them we must remember that we need the resulting set to be simply connected. 
 We get that per definition, since any cycles would be a waste of 'road'. You get a treelike structure. (And even if there were cycles, you can simply remove a few points untill there aren't) Quote:Also, where does the area of the convex hull come into all this? what relation does it have to the distances and number of points we are using? 
 To find the area of the convex hull you only need to look at the points that define the convex hull, so any points inside it aren't important. What we want is to connect those points simply, with as few 'coins' as possible. As I said that is a problem we dealt with before (I'll try to find the topic and link to it [e]here it is[/e]). So what's left is to find the relation between the 'connective distance' and the surface area. And we allready knows that the first scales with N and the latter with N^{2}, so really we're just looking for the greatest constant factor. (lim F(N)/(N^{2}) Quote:I have no clue as to how to even begin to prove that 120 degrees is the correct angle to use when trying to maximize the area of convex hulls... 
 Luckily you don't have to

« Last Edit: Dec 8^{th}, 2003, 1:45am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #21 on: Dec 8^{th}, 2003, 8:46am » 
Quote Modify

towr maybe we are not thinking of the same problem. it seems to me that all your comments apply when we fix a convex figure and try to minimize the number of coins needed to cover a simply connected region whose convex hull covers the convex set. On the otherhand, the problem i am considering here is: given n coins, overlap them so that they form a simply connected set. Now take the convex hull of that set. this last area is to be maximized, but the maximization also has to occur over all simply connected sets as well. In this latter problem, when n is large, the approach would be to consider only the diameters of the circles. also, most of your statements don't apply then since there are many things we must do all at once. It is not clear how to maximize over how many "endpoints" we should use, since we can not yet even prove for a fixed n points how to maximize convex hull per length of the underlying simply connected set. this is what i meant by the fact that it is not clear wher 120 degrees comes in... maybe this clears things up?

« Last Edit: Dec 8^{th}, 2003, 9:01am by pjay » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #22 on: Dec 8^{th}, 2003, 9:30am » 
Quote Modify

on Dec 8^{th}, 2003, 8:46am, pjay wrote:maybe this clears things up? 
 No.. I don't think you're reading what I say.. For any N coins there is some simply connected regions you can create. Any of these spans up a convex hull. Only points of that simply connected region that lie on the boundary matter for size and shape of the convex hull. So any that don't lie on the minimum size connected graph to those points are superfluous, and thus detract from the size of the area. Consequently our simply connected region mustn't include any of these superfluous points. You are throwing away a lot of information we have about the shape and character of the simply connected region. Many possibilities are excluded because only the area of the convex hull, given some N coins, matters. And certainly the connected region doesn't need to be maximized, we allready know exactly what size it is, N coins (2N units in length). What's left is just the shape. And the shape has to be a tree with 120 degree branchings, since that minimizes the length of 'road' it takes to connect (noncolinear) points (and they can not be colinear because of the convex hull, the middle points would be superfluous again) If you want to muddle around with all fancy shapes and sizes of simply connected regions that can't possibly maximize the area of it's convex hull, be my guest. But that's seem rather a waste of time..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



pjay
Newbie
Gender:
Posts: 30


Re: Maximum Coverage by Discs
« Reply #23 on: Dec 8^{th}, 2003, 11:45am » 
Quote Modify

on Dec 8^{th}, 2003, 9:30am, towr wrote: I don't think you're reading what I say.. 
 no need to get huffy. I AM reading what you are saying and i'm arguing that you are intertwining ideas in the wrong way. Just to illustrate. below i describe a tree who's convex hull has more area than an equilateral triangle, and uses the same total length in it's skeletal tree. Nowhere in my picture is there a 120 degree angle. attach two of the skeletons of eq triangles of the same size so that you get something that looks like ><. (here we start with all angles= 120 degrees but they will change soon). Notice that the convex hull of this shape gives you exactly the same area as an equilateral triangle that uses the same total length as its skeleton. Now slightly bend the 4 outside segments going towards a shape like , but not all the way. let [theta]+[pi]/2 be the angle between one of the legs and the middle segment. (in the first picture [theta]=[pi]/6, in the second [theta]=0) to prove we can obtain something more optimal than forming a skeleton of an eq. triangle, notice that the area of the convex hull of the shape described above is equal to 4cos[theta]+2sin[theta]cos[theta]. maximizing over [theta] gives us cos2[theta]=2sin[theta]. using cos2[theta]=12sin^2[theta] we see that sin[theta]=( [sqrt]31)/2. It is easy to check that this gives a max. this max is better than an equilateral triangle. Quote: You are throwing away a lot of information we have about the shape and character of the simply connected region. Many possibilities are excluded because only the area of the convex hull, given some N coins, matters. And certainly the connected region doesn't need to be maximized, we allready know exactly what size it is, N coins (2N units in length). What's left is just the shape. And the shape has to be a tree with 120 degree branchings, since that minimizes the length of 'road' it takes to connect (noncolinear) points 
 while i agree that we should use a tree, the above statement cannot be used to say that we must always have 120 degree angles in the tree we use. I hope I've illustrated that.

« Last Edit: Dec 8^{th}, 2003, 11:47am by pjay » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Maximum Coverage by Discs
« Reply #24 on: Dec 8^{th}, 2003, 2:02pm » 
Quote Modify

on Dec 8^{th}, 2003, 11:45am, pjay wrote:to prove we can obtain something more optimal than forming a skeleton of an eq. triangle, notice that the area of the convex hull of the shape described above is equal to 4cos[theta]+2sin[theta]cos[theta]. maximizing over [theta] gives us cos2[theta]=2sin[theta]. using cos2[theta]=12sin^2[theta] we see that sin[theta]=( [sqrt]31)/2. It is easy to check that this gives a max. this max is better than an equilateral triangle. 
 I get (2 sin[phi])*(2 + 2 cos[phi] ), where [phi] is measured as half the angle between the legs. The expression is maximized for [phi] = [pi]/3 (so twice that is 120 degrees) And so they're both 3 [sqrt]3 at the maximum as far as I can tell.. Note that such a rectangle can allways be made by putting two isosceles triangles together in such a way. So if an equilateral triangle is optimal for the triangular case it has to be optimal for this rectangular case. (And of course the rectangle has 4 times the area of one of the triangles it's made up of, and thus the same as such a triangle that's scaled in both dimensions by a factor 2) Quote:hmm.. yeah.. sorry about that. I get that sometimes. Feel free to tell me off when I do.. Quote:I AM reading what you are saying and i'm arguing that you are intertwining ideas in the wrong way. 
 And I strongly disagree with that..

« Last Edit: Dec 8^{th}, 2003, 2:25pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



