i have no Idea how i can do this. I guess it is 8*8 = 64, but that isn't the right answer:
What is the number of segments in the picture below? Each segment joins two circles.
[Math] the number of segments in the picture
algebra-precalculuscombinatoricsgraph theory
Related Solutions
Summary
For the first part of question, the answer is $$\binom{8}{3} + 4\binom{8}{4} + 5\binom{8}{5} + \binom{8}{6} = 644$$ The number pointed out by bof in one of hir comments.
For the second part, if we interpret the term "segment" as one of the $\binom{8}{2} = 28$ edges among the $8$ vertices, the answer will be $583$. This is achieved by removing 3 consecutive edges from the perimeter of the circle. For example, removing edges $12$, $23$ and $34$ will left us with $583$ triangles.
Part I - number of triangles.
Let us switch to how to derive the answer for the first part of question analytically.
Instead of $8$, consider the generalization of placing $n$ red dots on a circle, form a complete graph from them and then count the number of triangles formed by these lines. We further assume the red dots are in general position so that no three lines intersect at the same point (except at the red dots). As we can see below, this assumption is crucial.
WOLOG, we will label the $n$ red dots by $1, \ldots, n$ and they are placed on the circle in counterclockwise manner.
A triangle consists of 3 sides and each side is lying on a line formed by two red dots. Since it is possible some lines are sharing red dots, a triangle may involve $m$ red dots where $3 \le m \le 6$.
$\hspace0.5in$ 
Case 1. $m = 3$
There are $\binom{n}{3}$ ways to pick $3$ red dots $\{ a, b, c \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c \le n $. Given $a, b, c$, it is clear every red dot is shared by $2$ lines and there is only one way to form a triangle with the three lines $\{ ab, bc, ac \}$ (fig $1a$).
This means there area $\binom{n}{3}$ triangles for $m = 3$.
Case 2. $m = 4$,
There are $\binom{n}{4}$ ways to pick $4$ red dots $\{ a, b, c, d \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d \le n$. Given $a, b, c, d$, there are two possibilities, either one of them connects to all three lines (fig $2a$), this leads us nowhere or two of the red dots are shared by two lines. Consider the case $a$ is one of these two red dots and let's enumerate the possibilities:
$c$ is the other red dot, there are two possible line arrangements $\{ ac, cd, ab \}$ or $\{ ac, bc, ad \}$ (fig. $2b)$. However neither of them forms a triangle inside the circle.
$b$ is the other red dot, there are two possible line arrangements again $\{ ab, bc, ad \}$ (fig $2c$) and $\{ ab, bd, ac \}$ (fig $2d$). Only the second configuration forms a triangle inside the circle.
$d$ is the other red dot, this is similar to the above sub case with $d, a, b, c$ taking the roles of $a, b, c, d$. Among the two possible ine arrangements , only one of them forms a triangle inside the circle. If you loop over other possibilities of the two red dots which share lines. We find there are totally $4$ configuration for each choice of $(a, b, c, d)$.
This means there are $4 \binom{n}{4}$ triangles for the $m = 3$ case.
Case 3. $m = 5$
There are $\binom{n}{5}$ ways to pick $5$ red dots $\{ a, b, c, d, e \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d < e\le n$. Given $a, b, c, d, e $, it is clear one any only one of the red dots are shared by two lines. Consider the case $a$ is that distinguished red dots. There are six possible line arrangements $$ \{ ab, ac, de \} (\text{fig } 3a),\quad \{ ab, ad, ce \} (\text{fig } 3b),\quad \{ ab, ae, cd \} (\text{fig } 3c),\\ \{ ac, ad, be \} (\text{fig } 3d),\quad \{ ac, ae, bd \} (\text{fig } 3e),\quad \{ ad, ae, bc \} (\text{fig } 3f) $$ and only of them $\{ ac, ad, be \}$ forms a triangle inside the circle.
Since there are 5 possible ways to pick the distinguished red dots, there are $5\binom{n}{5}$ ways for the $m = 5$ case.
Case 4. $m = 6$
There are $\binom{n}{6}$ ways to pick $6$ red dots $\{ a, b, c, d, e, f \}$ out of $n$ red dots. WOLOG, we can assume $1 \le a < b < c < d < e < f\le n$. Given $a, b, c, d, e, f$, there are $15$ ways of grouping them into pairs and form $3$ lines. It is easy to see any line arrangement that contains neighboring pair $ab, bc, cd, de, ef, af$ does not form a triangle inside a circle (e.g. fig $4a$). This eliminate $11$ of them and we are left with $4$ line arrangements. $$\{ ac, be, df \},\quad \{ ad, be, cf \},\quad \{ ad, bf, ce \},\quad \{ ae, bd, cf \}$$ If you draw these $4$ arrangements on a piece of paper, you will notice the $1^{st}$, $3^{rd}$ and $4^{th}$ arrangement all looks like fig $4b$. They also won't produce any triangle inside the circle. This leaves us with the $2^{nd}$ line arrangement $\{ ad, be, cf \}$. There are two possibilities. The 3 lines either form a triangle inside the circle (e.g. fig $4c$) or intersect at a single point. Since we have assumed the last case will not happen. This means for each choice of $\{ a, b, c, d, e, f \}$, there is one and only one way to join them to get a triangle.
As a consequence, there are $\binom{n}{6}$ ways for the $m = 6$ case.
Combine these four cases, we can conclude the number of triangle for general $N$ is given by
$$\binom{n}{3} + 4\binom{n}{4} + 5\binom{n}{5} + \binom{n}{6}$$
Part II - maximum number of triangles remain after one remove 3 segments.
This is done by brute force. I write a program to locate all $644$ triangles and proceed to check the effect on removing any one of the $28$ edges. Let $N_{ab}$ be the number of triangles destroyed when we remove the edge $ab$, we have
$$\begin{array}{r:l} N_{ab} & ab\\ \hline 21 & 12, 23, 34, 45, 56, 67, 78, 18\\ 66 & 13, 24, 35, 46, 57, 68, 17, 28\\ 99 & 14, 25, 36, 47, 58, 16, 27, 38\\ 111 & 15, 26, 37, 48 \end{array}$$
Since $3 \times 21 < \min(66,99,111)$, the configuration which maximize the number of triangles remain is formed by removing three consecutive edges on the perimeter of the circle (i.e those from the first row of above table).
Using rotational symmetry, we can assume $18$ is one of the three edges to go. We only need to go through $\binom{7}{2} = 21$ pairs of edges from the set $\{ 12, 23, 34, 45, 56, 67, 78 \}$ to identify the optimal configurations.
First, note that the common mathematical terms for the objects you are dealing with are: (plane, undirected) graph for your data set, vertex for a connector, and edge for a segment. Also, if a vertex $w$ is joined to a vertex $v$ by an edge, we say that $v$ is a neighbour of $w$.
Furthermore, for our purposes a path is a sequence $(v_1, \dotsc, v_n)$ of vertices such that $v_i, v_{i+1}$ are connected by an edge for every $1 \leq i < n$, and a cycle is a path where $v_1 = v_n$ and no other vertex appears twice.
Now, from what you say you aren't assuming that your graph is connected, i.e. that every two vertices can be the endpoints of a path. Thus it isn't clear to me how you are detecting when a polygon is contained in another one to which it isn't connected.
Anyway, I'm going to propose a simpler recursive algorithm to detect every cycle in your graph. Those are precisely the boundaries of all the polygons contained in the graph. Then you can determine the "valid" polygons in various ways. For example, a somewhat inefficient way would be:
- For every polygon A:
- For every polygon B:
- If $A \subset B$: continue
- Subtract $A \cap B$ from $A$ and add back $\partial B \cap A$
Now, to detect the cycles you can do as follows:
- Set every vertex as
not visited- Create an empty path $P$
- Pick a random
not visitedvertex $w$- Set $w$ as
visitedand append it to $P$- For every neighbour $v$ of $w$:
- Create a copy $P'$ of $P$
- Set $v$ as
visitedand append it to $P'$- If $v$ was already in $P'$, return the sub-path that starts and ends with $v$
- Repeat from 5 with $w := v$ and $P := P'$
- If there are some
not visitedvertices left repeat from 2, otherwise we're done
Best Answer
Look at the middle line of points formed by the intersections of the line segments. Count how many segments run through each point, counting the left- and rightmost points as having one segment intersecting them.
Each consecutive point will have one more segment intersecting it than the last until you get to the middle; then the number works its way back down. You will notice that if you count this way, you will not count any segment more than once, since a segment cannot intersect more than one point.
As you might have guessed, this is equivalent to