At work there is a large poster on the wall that started out as 30 point arranged (equidistant) in a circle. Each point has a line connecting it to every other point. The little polygons bounded by these lines were colored in, one at a time, as people visited the room which the poster was in. They number perhaps a few dozen thousands. Can anyone tell me how many there are and how to compute that?
Thanks!
Here’s a cool little site that illustrates your graph. I can say the “number of edges” will be:
(30 * 29) / 2 or 435. But how many enclosed regions?
Here’s a cool little cite that illustrates your graph. I can say the “number of edges” will be:
(30 * 29) / 2 or 435. But how many enclosed regions?
http://www.utc.edu/~cpmawata/petersen/lesson4.htm
(Note: This cite works with my NS but not my IE.)
The maximum number of regions (including not just the polygons but also the bits partly bounded by an arc of the circle) obtained by 30 points (not necessarily evenly spaced) is given by 1 + C(30,2) + C(30,4), where the C expressions are binomial coefficients. [See this discussion at The Math Forum] This is equal to 27,841.
You lose some regions when you have three or more chords intersecting in a single point, as you have on your poster. I don’t know how to figure how many you lose, though.
The figure you’re describing is the complete graph on 30 vertices, or K[sub]30[/sub]. If it were planar (capable of being drawn on a piece of paper with no edges crossing) I could give you an estimate, but it’s not. However, the name might give you something to google on.