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?