How do I achieve this with the smallest number of circles? That is to say, how can I do this with the least overlap between them? I have the suspicion that

**Spoiler:**

But I'm not sure.

**Moderators:** jestingrabbit, Moderators General, Prelates

I have a plane that I want to cover with circles. Circles can overlap, but every point on the plane must be inside at least one circle.

How do I achieve this with the smallest number of circles? That is to say, how can I do this with the least overlap between them? I have the suspicion that

**Spoiler:**

But I'm not sure.

How do I achieve this with the smallest number of circles? That is to say, how can I do this with the least overlap between them? I have the suspicion that

But I'm not sure.

- EdgarJPublius
- Official Propagandi.... Nifty Poster Guy
**Posts:**3642**Joined:**Tue Oct 09, 2007 4:56 am UTC**Location:**where the wind takes me

can you not just **Spoiler:**

Roosevelt wrote:I wrote:Does Space Teddy Roosevelt wrestle Space Bears and fight the Space Spanish-American War with his band of Space-volunteers the Space Rough Riders?

Yes.

-still unaware of the origin and meaning of his own user-title

That's it, overlap 6.

Cover the plane with hexagons. The hexagons conected end-on-end should cover everything. Now draw the circle on each hexagon, from the center of the hexagon to one the vertices.

Cover the plane with hexagons. The hexagons conected end-on-end should cover everything. Now draw the circle on each hexagon, from the center of the hexagon to one the vertices.

Now these points of data make a beautiful line.

How's things?

-Entropy is winning.

How's things?

-Entropy is winning.

EdgarJPublius wrote:can you not justSpoiler:

Er... I forgot to mention that all the circles are of the same, finite size.

And Govalent, have you a proof?

This post had objectionable content.

Everything from here up is useless and shouldn't have been included. -G

3) I would agree that the hexagon thing works. Regular tilings are triangular, square and hexagonal. It would be easy to just check each one and see which overlaps the least, but, instinctively, I would say the circumscribed circles of hexagons are the best choice.

Everything from here up is useless and shouldn't have been included. -G

3) I would agree that the hexagon thing works. Regular tilings are triangular, square and hexagonal. It would be easy to just check each one and see which overlaps the least, but, instinctively, I would say the circumscribed circles of hexagons are the best choice.

EdgarJPublius wrote:can you not justSpoiler:

You can't have a single arbitrarily large circle. It makes no sense. Either it's finite size, or it's not a circle. "Arbitrarily large" generally applies to sets where the size of individual elements is unbounded. It can't really be used to talk about a single, finite object like a circle.

All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

How do you define "least overlap"? All coverings will have an overlap that is infinite, of the same cardinality.

One way is to measure it as the limit of the quotient of overlap of coverings of finite regions, letting the regions tend to the whole plane, but I'm not sure you'd get the same result no matter how you choose the regions (though it seems plausible).

One way is to measure it as the limit of the quotient of overlap of coverings of finite regions, letting the regions tend to the whole plane, but I'm not sure you'd get the same result no matter how you choose the regions (though it seems plausible).

You would as long as the shapes of the regions were reasonably sensible (if you actively tried to find a set of regions of increasing size whose limit for the quotient was anomalous, you definitely could) - unless perhaps it was a particularly nasty sort of irregular tiling, which seems to me unlikely to be optimal.

This is a placeholder until I think of something more creative to put here.

Torn Apart By Dingos wrote:How do you define "least overlap"? All coverings will have an overlap that is infinite, of the same cardinality.

One way is to measure it as the limit of the quotient of overlap of coverings of finite regions, letting the regions tend to the whole plane, but I'm not sure you'd get the same result no matter how you choose the regions (though it seems plausible).

I imagine you would do it in the same way that you define what percentage of the plane a non-overlapping tiling covers.

All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

It'd be helpful if you said how that is done. I assume it's defined as the ratio of overlap of a single tile. But a circle covering of the plane needn't be tileable, so I don't know how it could be generalized.

I suppose you could define it by taking a convex, absorbent, measurable subset A of the plane (like a circle, or a nondegenerate rectangle), and then for each natural number n check to see what the fraction of area nA has that consists of overlap in the circles. You want to minimize the limit of this fraction as n approaches infinity, assuming that it is well-defined.

Edit: Added convexity.

Edit: Added convexity.

Last edited by Owehn on Sat Oct 27, 2007 8:41 pm UTC, edited 1 time in total.

[This space intentionally left blank.]

Torn Apart By Dingos wrote:It'd be helpful if you said how that is done. I assume it's defined as the ratio of overlap of a single tile. But a circle covering of the plane needn't be tileable, so I don't know how it could be generalized.

Well, in the case that the packing is periodic, it's obvious. If it isn't, then I don't actually know if you can even calculate it.

All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

The translation symmetries of the plane are an amenable group, R^{2}, which therefore have a folner sequence, with the nth term something like F_{n}="all the points in the plane that are less than n from (0,0)" and then have the area of the overlap, O, be

lim_{n to infty} m(F_{n} intersect O)/m(F_{n})

where m is normal lebesgue measure. This should be defined for all the sets we care about, and is translation invariant, which is another bonus.

That said, I expect the proof for the obvious tiling is going to be extremely non trivial.

lim

where m is normal lebesgue measure. This should be defined for all the sets we care about, and is translation invariant, which is another bonus.

That said, I expect the proof for the obvious tiling is going to be extremely non trivial.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

This would appear to be closely related to the circle packing problem, which according to http://mathworld.wolfram.com/CirclePacking.html, was solved in 1940 (which also means that someone has figured out how to define a density of packing on the plane that makes sense).

Perhaps a doable attack would be to try to reduce this circle covering problem to the circle packing problem?

Perhaps a doable attack would be to try to reduce this circle covering problem to the circle packing problem?

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

Owehn: What are absorbent sets?

jesting: I'm not able to follow that because I don't know what amenable groups or folner sequences are (amenable was on wikipedia but I couldn't find folner sequences). Was that some kind of proof that the way you measure the covering will not depend on what the sequence F_n are?

jesting: I'm not able to follow that because I don't know what amenable groups or folner sequences are (amenable was on wikipedia but I couldn't find folner sequences). Was that some kind of proof that the way you measure the covering will not depend on what the sequence F_n are?

An absorbent subset A of a vector space over K is one with the property that for every element x of the vector space, there is a number k in K such that x/k is an element of A (that is, x is in kA). The idea is that as as you let k range over K, kA "absorbs" the whole vector space. Absorbent sets are also called absorbing.

An example of an absorbent set for R^2 is a disc around the origin.

An example of an absorbent set for R^2 is a disc around the origin.

[This space intentionally left blank.]

- MartianInvader
**Posts:**788**Joined:**Sat Oct 27, 2007 5:51 pm UTC

I had to register just to comment on this.

You never said all the circles had to be the same size. If they can get very small, you can cover the plane with a fractal-like pattern of circles so that each circle intersects only four others, and each point of the plane is contained in no more than two circles.

You can do this by tiling the plane with squares, then inscribing a circle in each square. The space outside the circles now looks like a bunch of regions each with four bounding arcs, and you can inscribe a circle in each of them. The remaining space now looks like a bunch of triangles (well "triangles" with arcs instead of straight sides), and you can inscribe a circle in each of those, leaving more triangles uncovered. Continue this process to inifinity and each point in the plane will eventually be engulfed, while each circle intersects no more than 4 others (each intersection is, in fact, a single point), and no 3 circles all intersect each other. The area of intersection also has measure zero (heck, it consists of a countable number of points). The final tiling looks sort of fractal-like (not unlike http://www.xkcd.com/17/). I think if you adjust the process a bit you can even make it so each circle only touches 3 others.

Okay, well, I'll go post in the intro thread now.

EDIT: Whoops, you did mention a few posts later that all the circles were of the same, finite size. Nevermind then.

You never said all the circles had to be the same size. If they can get very small, you can cover the plane with a fractal-like pattern of circles so that each circle intersects only four others, and each point of the plane is contained in no more than two circles.

You can do this by tiling the plane with squares, then inscribing a circle in each square. The space outside the circles now looks like a bunch of regions each with four bounding arcs, and you can inscribe a circle in each of them. The remaining space now looks like a bunch of triangles (well "triangles" with arcs instead of straight sides), and you can inscribe a circle in each of those, leaving more triangles uncovered. Continue this process to inifinity and each point in the plane will eventually be engulfed, while each circle intersects no more than 4 others (each intersection is, in fact, a single point), and no 3 circles all intersect each other. The area of intersection also has measure zero (heck, it consists of a countable number of points). The final tiling looks sort of fractal-like (not unlike http://www.xkcd.com/17/). I think if you adjust the process a bit you can even make it so each circle only touches 3 others.

Okay, well, I'll go post in the intro thread now.

EDIT: Whoops, you did mention a few posts later that all the circles were of the same, finite size. Nevermind then.

Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

draw a citcle around the fusilage

you have instant coverage with 2 circles

you have instant coverage with 2 circles

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

Wikipedia also required that x is in nA for all |n|>=k. Will that do what we want though?Owehn wrote:An absorbent subset A of a vector space over K is one with the property that for every element x of the vector space, there is a number k in K such that x/k is an element of A (that is, x is in kA). The idea is that as as you let k range over K, kA "absorbs" the whole vector space. Absorbent sets are also called absorbing.

An example of an absorbent set for R^2 is a disc around the origin.

The set {ax : |x|<1, a = angle(x), 0<a<=2pi} is absorbent in R^2 but can never be inflated to cover the unit disc. I'd rather use a set that covers some neighborhood of 0.

Definitions vary, so usually people use asborbing + convex, which will guarantee the property you want. In fact, I'll update my previous post with that condition.

[This space intentionally left blank.]

- jestingrabbit
- Factoids are just Datas that haven't grown up yet
**Posts:**5967**Joined:**Tue Nov 28, 2006 9:50 pm UTC**Location:**Sydney

Torn Apart By Dingos wrote:jesting: I'm not able to follow that because I don't know what amenable groups or folner sequences are (amenable was on wikipedia but I couldn't find folner sequences). Was that some kind of proof that the way you measure the covering will not depend on what the sequence F_n are?

The amenable groups article on WP isn't too bad (though not discussing folner sequences is an horrendous omission). It basically insists that there is a "mean" on the space of bounded functions,

where a mean, m, is such that m(1

So, I just say that R

I don't know if those convex, absorbent sets give you the same deal, but I do know that the means that amenable groups give us exactly what we want. You could easily add the group of 2d rotations, the circle group, to the group of translations R

The mean of the sum of the indicator values of the discs is then

lim

If you can tile the plane with some repeating segment, as you can with the assumed answer, then you just take the area of all the disc parts and divide by the area of the tile. I get a value of 2*π*3

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

MartianInvader: If the sizes could vary, then we could cover the plane with no overlaps, and is thus a trivial problem. This is likely why it was formulated as it was.

With the fractal covering plan? Wouldn't that leave out a Cantor dust type set of uncovered points?quintopia wrote:MartianInvader: If the sizes could vary, then we could cover the plane

with no overlaps, and is thus a trivial problem. This is likely why it

was formulated as it was.

- MartianInvader
**Posts:**788**Joined:**Sat Oct 27, 2007 5:51 pm UTC

I'm not certain, but it seems to me that if you're talking about open circles, then the fractal-ish pattern would leave out points, but if you're talking about closed circles, then everything gets covered. Neither was specified at the start of the problem, so I was using closed circles.

quintopia: Yeah, I realized that the question was phrased in a non-trivial way after I posted, hence the edit at the end of my post.

quintopia: Yeah, I realized that the question was phrased in a non-trivial way after I posted, hence the edit at the end of my post.

Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

True. But yes, equal sized circles is a better problem.MartianInvader wrote:I'm not certain, but it seems to me that if you're talking about open circles, then the fractal-ish pattern would leave out points, but if you're talking about closed circles, then everything gets covered.

- Torn Apart By Dingos
**Posts:**817**Joined:**Thu Aug 03, 2006 2:27 am UTC

Okies.

Are you sure? With open circles, obviously the boundary will not be included, but will no other points be missed?

MartianInvader wrote:I'm not certain, but it seems to me that if you're talking about open circles, then the fractal-ish pattern would leave out points, but if you're talking about closed circles, then everything gets covered.

Are you sure? With open circles, obviously the boundary will not be included, but will no other points be missed?

I'm pretty certain no points would be left out, but I'm not sure how to prove it.

- phlip
- Restorer of Worlds
**Posts:**7551**Joined:**Sat Sep 23, 2006 3:56 am UTC**Location:**Australia-
**Contact:**

If you use solely open circles, then it'd be impossible to completely cover the plane without overlaps:**Spoiler:**

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};`

void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}

Yes yes, but can you find a counter example to the closed set covering?

Yes.

Start with three congruent disks, pairwise mutually externally tangent, with one on the bottom, one to the top left, one to the top right, and consider the triangle-like region between them. You're removing disks from this region in the "fractal-like" way that was described above.

I'm going to assign to each sequence of the symbols 1, 2, and 3, a point in that region with all the open disks removed. 1 means go up, 2 means go down and right, 3 means go down and left. For example, a sequence starting with 1 represents some point in the top "third" of the region. A sequence starting with 22 represents some point in the bottom right "ninth". Then a point represented by a sequence is just the intersection (ranging over k) of the (closed) sets that it is limited to by the first k symbols in the sequence.

Now, this maps to a point on one of the circles if and only if the sequence eventually ends up only having two of the three symbols in it. So, an example of a point that's in the region with all the closed disks removed is the one represented by 123123123123... .

This is pretty much the exact same issue as with the Sierpinski gasket. The thing you get by drawing the lines isn't the same as the thing you get by removing the triangles.

Start with three congruent disks, pairwise mutually externally tangent, with one on the bottom, one to the top left, one to the top right, and consider the triangle-like region between them. You're removing disks from this region in the "fractal-like" way that was described above.

I'm going to assign to each sequence of the symbols 1, 2, and 3, a point in that region with all the open disks removed. 1 means go up, 2 means go down and right, 3 means go down and left. For example, a sequence starting with 1 represents some point in the top "third" of the region. A sequence starting with 22 represents some point in the bottom right "ninth". Then a point represented by a sequence is just the intersection (ranging over k) of the (closed) sets that it is limited to by the first k symbols in the sequence.

Now, this maps to a point on one of the circles if and only if the sequence eventually ends up only having two of the three symbols in it. So, an example of a point that's in the region with all the closed disks removed is the one represented by 123123123123... .

This is pretty much the exact same issue as with the Sierpinski gasket. The thing you get by drawing the lines isn't the same as the thing you get by removing the triangles.

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Does this counterexample extend to all fractal patterns? For example, what if the area between 3 circles was filled with a triangle of 3 in the opposite orientation?

Kerberos wrote:EdgarJPublius wrote:can you not justSpoiler:

Er... I forgot to mention that all the circles are of the same, finite size.

And Govalent, have you a proof?

...one large circle would be technically be the same size (as itself) and finite... maybe you should define the problem more accurately...

Let epsilon be less than zero...

1 finite circle cannot cover the plane, not matter how large. The problem is well-defined.

So what if you iterated the fractal for n steps and then threw just-big-enough disks around the uncovered regions? I don't see why this wouldn't result in the fraction of the plane covered by >1 disk being arbitrarily small. Yes, this breaks the "same size" rule, but it's still an interesting idea.

So what if you iterated the fractal for n steps and then threw just-big-enough disks around the uncovered regions? I don't see why this wouldn't result in the fraction of the plane covered by >1 disk being arbitrarily small. Yes, this breaks the "same size" rule, but it's still an interesting idea.

Yeah, it's pretty easy to see that that works. If you want to cover a region bounded by three circles, do the iterated fractal, and add e*2^{-n} to the radius of the n'th disk (make it open). This adds a finite area to the disks (I'm too lazy to calculate what it is), and this area approaches zero as e goes to 0. So you can get arbitrarily good coverings. You can even take a finite subcover of this open cover of a compact region, so that you don't need arbitrarily small disks.

Next question: If you're allowed circles ranging in radius from 1 to R, how little overlap can you get?

Next question: If you're allowed circles ranging in radius from 1 to R, how little overlap can you get?

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Users browsing this forum: No registered users and 4 guests