# Understand and an algorythm to Maximize number of triangles from a set of points on XY plane

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. :)

-
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
I have tried to be as clear as possible. The example was to clarify and add details to the introduction. This is the question with it's restrictions. Your comment contains no solution and no contribution... – iAmOren Jan 15 at 2:08