'Counting number of ways to make a 3 Partition of n dots in a triangle such that each partition fit in a "Y" shape. (More description below)
I want to find an algorithm to tackle this problem but I have no idea what this problem is even called so I can't google it.
Problem:
There is a triangle, and inside the triangle there are n dots. For example, as below.

Now assume 3 sides of triangle are rubber bands and dots are nails on the wall. We tuck each rubber bands into some dot(s). But each rubber bands must be convex towards the center of triangle. Also, there should be no intersection of any 2 rubber bands apart from the 3 vertices of original triangle. Also, there should not be any remaining dot inside the polygon formed by 3 rubber bands. How many valid arrangement of rubberbands, such that all given conditions are satisfied, are there?
Here, in this picture, the leftmost picture is the original state, 2nd picture is a valid composition, 3rd is invalid since blue and red rubber bands intersect, 4th is invalid since there is a nail remaining inside red-blue-green polygon
My approach: After some thoughts: I guessed that if we pick an arbitrary location inside the triangle which is not one of the given dots(nails), and then we make a Y shape starting from that location towards 3 vertices of outer triangle, that is guaranteed to make a unique valid arrangement of rubber bands, if we imagine that each pair of 2 neighboring edges of Y shape is a rubberband and then we release those bands. They will sort themselves out to form a valid arrangement with elasticity.
So from each 3 vertices of triangle, I draw a line towards all n dot(nails). And then for each polygon partitions that are created by those lines and/or 3 sides of triangle(approx n^3 polygon partitions in total), I can make exactly 1 valid composition by picking any point in the polygon and making Y shape.
For example, if I pull rubber bands to form a y-shape as in the left picture, I can then make a valid composition by releasing those rubber bands, as in the right picture.
However, the problem is that 2 or more polygons may yield same valid composition, so we will count more than the correct answer.
For example, if there are only 2 dots(nails), we could make a bunch of polygon partitions by connecting lines(colored brown) starting from each 3 vertices of triangle to 2 dots(nails). so there are 17 partitions. each 17 partitions would yield a valid composition but the answer would be 6. (3 cases where 2 dots go under same rubber band, 3 cases where 1 dot goes under a band and the other dot goes under the other band.)
So I drew several small examples and tried to figure out a pattern to make an algorithm to de-duplicate it and I kind of see a pattern but can't really formulate it into a pseudo code. Any help is appreciated.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|



