Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given: Set of points (x, y) Looking to: Maximize count of triangles that can be formed. Each triangle which is enclosed within another (with/without shared edge) will be counted again. Specifics on which triangle will be counted: Order of aplying edges matters. Direction of edges matters. Edges cannot cross aother edges. Points already surrounded completely with triangles cannot be connected to any point anymore, but may be connected from another point that is not completely surrounded by triangles. From each point, a maximum of 8 edges can originate.

Say, triangle ABC with another point D inside of it. Connecting each point to all others creates 3 inner triangles + 1 outer. If the count is 3 or 4 is explained as follows: If outer triangle was formed first, D cannot be connected to A, B or C, howeve, D can be connected from A, B, and C. Best solution: triangle ABD, then ABC, then edge CD (not DC) crates 2 more, CDA and CDB = count of 4 triangles. If CDA and CDB are formed first, then edge AB or BA is applied, only one more triangle is counted, namely: ABC. ABD is NOT counted as it is SMALLER than ABC.

Another example: Say, points L(eft) and R(ight) are aligned horizontaly. above the would-be-edge are a set of points U(p)1-Un. Connecting U1 to U2, U2 to U3, ..., Un-1 to Un, and then L to each U and R to each U will result in 2*(n-1) triangles. Then connectine L to R will only count one more triangle, namely: LRUn, with total count of 2*(n-1)+1. Insted, connecting LRU1, then LRU2, then U2 to U1, and repeating (LRU3, U3 to U2) until lastly connecting LRUn, Un to Un-1, will result in 3*(n-1)+1 triangles.

I am looking for an idea of how to approach the matter in order to create an algorythm that is given set of point and returns an ordered list of edges (from which point to which point) that will give the maximum count of triangles. I am familiar with recursion.

Thank you! Oren. :)

share|cite|improve this question
This is a really confusing way to construct and count triangles. In the first example, why do $CDA$ and $CDB$ count in the first solution when $ABD$ doesn't count in the second? Why doesn't the spec mention this stuff about smaller triangles not counting? Is there any specific motivation for these strange restrictions? –  user2357112 Jun 30 '14 at 2:17

1 Answer 1

Sounds like someone is looking for an algorithm to maximize field count in Ingress :)

Having thought about the problem for a bit, I think the task can be split in a few parts:

1) Find a set of links (edges) that create the maximum possible number of triangles. At this stage, the only restriction is that the edges cannot cross. There is often more than one solution for this. I'm sure brute force can do this given enough time. However, a LOT of time may be required.

2) Once a solution is chosen/found, determine the sequence of links in order to comply with the other requirements (a new link can create triangles inside pre-existing triangles, but not a new triangle inside another new triangle). This part can also be done by brute force, but again may take too long.

I have a matlab script that tests a given sequence of links and calculates how many valid triangles are formed (and how many triangles are "lost"). For a set of 25 nodes, a sequence (about 50 links and 50 triangles) takes about 0.3 seconds to run and validate, which is too long if we're trying to brute-force all possible solutions...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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