Circles on a plane

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
Kerberos
Posts: 189
Joined: Sun Oct 21, 2007 1:41 am UTC
Location: Male

Circles on a plane

Postby Kerberos » Wed Oct 24, 2007 11:41 pm UTC

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:
each circle intersects six other circles, and every intersection is between three circles. Like this:
Image

You might be able to tell that I don't have any software that lets me draw overlapping circles.


But I'm not sure.

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

Re: Circles on a plane

Postby EdgarJPublius » Thu Oct 25, 2007 1:11 am UTC

can you not just
Spoiler:
use one arbitrarily large circle?
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

User avatar
Govalant
Posts: 249
Joined: Mon Sep 17, 2007 2:50 am UTC
Location: Rosario, Argentina
Contact:

Re: Circles on a plane

Postby Govalant » Thu Oct 25, 2007 2:26 am UTC

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.
Now these points of data make a beautiful line.

How's things?
-Entropy is winning.

User avatar
Kerberos
Posts: 189
Joined: Sun Oct 21, 2007 1:41 am UTC
Location: Male

Re: Circles on a plane

Postby Kerberos » Thu Oct 25, 2007 3:04 am UTC

EdgarJPublius wrote:can you not just
Spoiler:
use one arbitrarily large circle?

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

And Govalent, have you a proof?

bittyx
Posts: 194
Joined: Tue Sep 25, 2007 9:10 pm UTC
Location: Belgrade, Serbia

Re: Circles on a plane

Postby bittyx » Thu Oct 25, 2007 4:26 am UTC

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.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Circles on a plane

Postby Token » Thu Oct 25, 2007 8:31 am UTC

EdgarJPublius wrote:can you not just
Spoiler:
use one arbitrarily large circle?

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.

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

Re: Circles on a plane

Postby Torn Apart By Dingos » Thu Oct 25, 2007 2:12 pm 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).

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Circles on a plane

Postby Robin S » Thu Oct 25, 2007 2:44 pm UTC

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.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Circles on a plane

Postby Token » Thu Oct 25, 2007 3:48 pm UTC

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.

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

Re: Circles on a plane

Postby Torn Apart By Dingos » Thu Oct 25, 2007 5:04 pm 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.

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Circles on a plane

Postby Owehn » Thu Oct 25, 2007 6:25 pm UTC

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.
Last edited by Owehn on Sat Oct 27, 2007 8:41 pm UTC, edited 1 time in total.
[This space intentionally left blank.]

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Circles on a plane

Postby Token » Thu Oct 25, 2007 9:03 pm UTC

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.

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

Re: Circles on a plane

Postby jestingrabbit » Fri Oct 26, 2007 3:38 pm UTC

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

limn to infty m(Fn intersect O)/m(Fn)

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.

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Circles on a plane

Postby HenryS » Sat Oct 27, 2007 6:15 am UTC

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?

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

Re: Circles on a plane

Postby Torn Apart By Dingos » Sat Oct 27, 2007 9:49 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?

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Circles on a plane

Postby Owehn » Sat Oct 27, 2007 3:50 pm UTC

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.
[This space intentionally left blank.]

User avatar
MartianInvader
Posts: 780
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Circles on a plane

Postby MartianInvader » Sat Oct 27, 2007 6:12 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.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
4=5
Posts: 2073
Joined: Sat Apr 28, 2007 3:02 am UTC

Re: Circles on a plane

Postby 4=5 » Sat Oct 27, 2007 6:52 pm UTC

draw a citcle around the fusilage
you have instant coverage with 2 circles

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

Re: Circles on a plane

Postby Torn Apart By Dingos » Sat Oct 27, 2007 8:12 pm UTC

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.
Wikipedia also required that x is in nA for all |n|>=k. Will that do what we want though?

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.

User avatar
Owehn
Posts: 479
Joined: Tue Oct 09, 2007 12:49 pm UTC
Location: Cambridge, UK

Re: Circles on a plane

Postby Owehn » Sat Oct 27, 2007 8:38 pm UTC

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.]

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

Re: Circles on a plane

Postby jestingrabbit » Sun Oct 28, 2007 2:15 am UTC

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(1G)=1 (where 1G is the constant function on the amenable group G), m(sf + tg) = s(m(f)) + t(m(g)) (where f and g are real valued functions on G and s and t are real constants) and finally with m(f)>0 for f:G to R where f(x)>0 for all x in G. Think: m is something like an integral on LG.

So, I just say that R2 is an amenable group and demonstrate it by producing a folner sequence, which allows you to prove the existence of a mean m. In fact, if you take that formula from my earlier post, you will get the value of a mean on R2 for a subset of the plane, where you map that subset to its indicator function.

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 R2 and still have an amenable group, where we force the mean to behave well for rotations too. Either way, the idea of taking the mean of the sum of the indicator functions of the discs is what I want to go with. A formula for the mean of the sum of the indicators can be got at as follows, where I'll assume that the circles we use have radius 1. Let {(xi,yi)} be the set of all the centres of the circles, where i runs over the naturals. For r>0 let Nr = |{(xi,yi) : xi2+yi2<r2}| ie Nr is the number of circle centres inside the circle or radius r centred at the origin.

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

limr to ∞ r-2Nr

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-3/2 = 1.20919958 for the assumed answer. Note that all of these means will be over 1, as 1 is less than the sum of the indicators at any point as the discs must cover all points.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Circles on a plane

Postby quintopia » Sun Oct 28, 2007 10:21 pm UTC

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.

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Circles on a plane

Postby HenryS » Mon Oct 29, 2007 8:03 pm UTC

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.
With the fractal covering plan? Wouldn't that leave out a Cantor dust type set of uncovered points?

User avatar
MartianInvader
Posts: 780
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Circles on a plane

Postby MartianInvader » Mon Oct 29, 2007 9:32 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.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Circles on a plane

Postby HenryS » Mon Oct 29, 2007 9:50 pm UTC

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.
True. But yes, equal sized circles is a better problem.

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

Re: Circles on a plane

Postby Torn Apart By Dingos » Mon Oct 29, 2007 10:42 pm UTC

Okies.

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?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Circles on a plane

Postby quintopia » Mon Oct 29, 2007 11:12 pm UTC

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

User avatar
phlip
Restorer of Worlds
Posts: 7550
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Circles on a plane

Postby phlip » Wed Oct 31, 2007 12:47 pm UTC

If you use solely open circles, then it'd be impossible to completely cover the plane without overlaps:
Spoiler:
Consider a point P on the border of circle A. Clearly, P is not covered by that circle. If P is covered by, say, circle B, then, because circle B is open, there exists an open disc centred on P that is contained entirely within circle B. However, because P is on the boundary of circle A, any open disc centred on P will intersect with circle A. Thus circle A and circle B must intersect.

This of course generalises to "You cannot cover the plane with a union of disjoint bounded open sets"... and I'm not even sure if "bounded" is necessary... maybe just requiring that the set has boundary points at all...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Circles on a plane

Postby quintopia » Wed Oct 31, 2007 4:23 pm UTC

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

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Circles on a plane

Postby antonfire » Wed Oct 31, 2007 7:21 pm UTC

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.
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?

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Circles on a plane

Postby quintopia » Wed Oct 31, 2007 9:06 pm UTC

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?

User avatar
Zaraden
Posts: 30
Joined: Thu Nov 01, 2007 6:27 pm UTC
Location: Canada

Re: Circles on a plane

Postby Zaraden » Fri Nov 02, 2007 3:29 am UTC

Kerberos wrote:
EdgarJPublius wrote:can you not just
Spoiler:
use one arbitrarily large circle?

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...

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Circles on a plane

Postby quintopia » Fri Nov 02, 2007 3:30 am UTC

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.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Circles on a plane

Postby antonfire » Fri Nov 02, 2007 7:10 am UTC

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?
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?


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 10 guests