Euler plays Ingress

In the game Ingress you capture portals (by visiting real world locations), and then you can link pairs of portals together. You get points for doing that. If three portals are mutually linked with three links, forming a triangle, then they make a control field, and that’s a good thing if only because you get a lot of points for doing that. So if you’re trying to level up, one way is to find a lot of portals close together and circulate between them, capturing them and linking them.

One rule of linking, though, is that links can’t cross. If you want to link two portals, and a straight line segment between them intersects some other link, then tough luck: you can’t link them.

(Technically, if the Earth is regarded as a sphere, presumably links are great circle segments and control fields are spherical triangles. But for our purposes we pretend we’re working in a plane. Links are line segments, control fields are Euclidean plane triangles.)

So a question you might ask is, for some collection of portals, is there an optimal way to link them? Can you make more links or more control fields if you do it one way than if you do it another?

Answer: No. If you start creating links, and keep adding links until no more links are possible, then regardless of how you decide which links to make, you always get the same number of links, and the same number of control fields.

And how many is that?

You get the answer using the Euler characteristic. For any convex polyhedron,

F - E + V = 2

where F, E, and V are respectively the number of faces, edges, and vertices the polyhedron has. A cube, for instance, has 6 faces, 12 edges, and 8 vertices:

6 - 12 + 8 = 2 .

What do polyhedra have to do with portals? Well, the same idea applies to any connected planar graph (a graph with non crossing edges), which can be thought of as the shadow of a polyhedron, provided you realize every region of the plane bounded by edges is a face, including the region extending to infinity. So this graph

also has 6 faces, 12 edges, and 8 vertices, if you count as faces the central quadrilateral, the four quadrilaterals surrounding it, and the infinite region surrounding them.

Viewed as linked Ingress portals, though, it’s not maxed out; in fact, there are no control fields because none of the polygons are triangles. So you can add more links until you have, for instance

and now there are 11 faces, 17 edges, and 8 vertices; 11-17+8=2.

But to maximize links and control fields, all the polygons in the graph, except the external one, must be triangles. Each of the F-1 triangular faces has 3 edges. But E\ne 3(F-1), because where two triangles adjoin, a single edge is one of the bounding edges of both triangles. It serves as two edges, in a way. On the other hand, edges of triangles along the boundary are shared with the external polyhedron. So if we regard the external polyhedron as contributing zero edges then each internal triangle (not along the boundary) contributes 3/2 edges, and each boundary triangle contributes 2 edges. Or

E = \frac{3}{2}N + \frac{1}{2}N_b

where N=F-1 is the number of triangles and N_b is the number of boundary triangles, which is the same as the number of edges or vertices in the bounding polygon (which is the convex hull of all the vertices). Solving for N,

N = \frac{2}{3}(E-\frac{N_b}{2})

Then combining with the Euler characteristic,

\frac{2}{3}(E-\frac{N_b}{2})+1-E+V = 2

or

E=3V-N_b-3

In the above diagram, V = 8 and N_b = 4 so E = 24-4-3 = 17, which is what we see. This tells us no matter how we link portals, once we’ve made all possible links, the number of links we end up with is the same. And the number of control fields, N, is

N = \frac{2}{3}(3V-N_b-3-\frac{N_b}{2}) = 2V-N_b-2

And again in the above diagram, N = 2\times 8-4-2 = 10 which is correct. No matter how we link a given set of portals, we end up with a fixed number of control fields. All that matters is the number of portals, and the number in the convex hull.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s