|
Dej Mar sure knows his formulas, there are in fact at most n*m*(m-1)+2 regions possible.
From Euler's formula we know that
V+F=E+2
where V, F, E denote the vertices, regions (faces) and edges of a map of regions. The formula is usually know for polyhedra, but it holds just as well for planar maps. The infinite outer regions counts as one region too.
To simplify things, assume our polygons have no "sharp" corners, but slightly rounded ones. This doesn't change the number of regions when we ensure it's just a tiny, tiny round. To make sure no regions are wasted, no three polygons should intersect at the same point. If they do, we could stretch and shift one of the polygons a tiny bit without affecting other regions. In that case, we'd have 2 vertices per edge, and 4 edges per vertex in our map. (The vertices are where polygons intersect) It follows E=2*V. This is why smooth polygons are handier, otherwise we had vertices with only 2 edges which makes things a little more complicated. If we insert this in the Euler formula and solve for F, we get
F=E-V+2=V+2
Look at that, we only have to count vertices now! Let's do that:
Two polygons can intersect in a maximum of 2n vertices. Since we have m*(m-1)/2 pairs of polygons, this gives a maximum of n*m*(m-1) vertices. Gives
F=n*m*(m-1)+2
Finally, one can easily see that the maximum number of vertices and thus the maximum number of regions can be obtained by using equally sized, centered polygons, where each one is slightly rotated versus the other. See also Jer's post.
|
