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