Say you have X points on a plane.

If you connect two points, you form a line. Connecting three points forms a triangle.

A line cannot cross a line, and a smaller triangle cannot be created inside a bigger one. Likewise, a line cannot be created inside an existing triangle. A bigger triangle can be created over a smaller one, or over a line, as long as no lines cross.

To connect two dots, you must have the key of the dot you are connecting TO, but you do not have to have the key of the dot you are connecting from. Once connected, the key of the dot you have been connecting to is spent and cannot be reused. You can have an infinite number of keys of any given dot.

A dot can be the edge of infinitely many triangles, but a triangle between three dots can only be created once - you cannot connect A, B and C more than once.

How would one compute the order of lines to be drawn to reach the maximum number of nested triangles?

In case this sounds familiar, it's about the game Ingress.

Edit: By "compute the order" I mean getting a result such as

  • A to B
  • B to Z
  • B to F
  • C to A
  • D to C
  • D to Z
  • ... etc

Until either the maximum number of triangles between the dots has been created, or until one has no more keys to use for connecting.

Am I correct in assuming the Delaunay triangulation calculates the maximum number of triangles in a set of points in such a way, and would just need to have the key number params applied?


This is not a complete answer, but I think the Delauny triangulation will give you what you're looking for (assuming infinite keys), because each triangle will have large area (since the angles are as large as possible) and so your intermediate control zones will be large.

If you don't have enough keys, though, you can do 'flips' (see the Wikipedia article to move edges away from portals where you're lacking keys to portals where you have extra. This will make the triangles more skinny, though.

  • $\begingroup$ The skinniness of the triangles is irrelevant - the only relevant factor is the number of final triangles. So 3 perfectly large triangles are less valuable than 4 super skinny ones and one covering all three. $\endgroup$ – Swader Apr 5 '13 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.