## Friday, September 16, 2016

### Non-crossing lines to connect points in a circle - GeeksforGeeks

Non-crossing lines to connect points in a circle - GeeksforGeeks
Consider a circle with n points on circumference of it where n is even. Count number of ways we can connect these points such that no two connecting lines to cross each other and every point is connected with exactly one other point. Any point can be connected with any other point.

```Consider a circle with 4 points.
1
2        3
4
In above diagram, there are two
non-crossing ways to connect
{{1, 2}, {3, 4}} and {{1, 3}, {2, 4}}.

Note that {{2, 3}, {1, 4}} is invalid
as it would cause a cross```

We need to draw n/2 lines to connect n points. When we draw a line, we divide the points in two sets that need to connected. Each set needs to be connected within itself. Below is recurrence relation for the same.
```Let m = n/2

// For each line we draw, we divide points
// into two sets such that one set is going
// to be connected with i lines and other
// with m-i-1 lines.
Count(m) = ∑ Count(i) * Count(m-i-1)
where 0 <= i < m
Count(0) = 1

Total number of ways with n points
= Count(m) = Count(n/2)
```
If we take a closer look at above recurrence, it is actually recurrence of Catalan Numbers. So the task reduces to finding n/2'th Catalan number.
`// A dynamic programming based function to find nth`
`// Catalan number`
`unsigned ``long` `int` `catalanDP(unsigned ``int` `n)`
`{`
`    ``// Table to store results of subproblems`
`    ``unsigned ``long` `int` `catalan[n+1];`

`    ``// Initialize first two values in table`
`    ``catalan[0] = catalan[1] = 1;`

`    ``// Fill entries in catalan[] using recursive formula`
`    ``for` `(``int` `i=2; i<=n; i++)`
`    ``{`
`        ``catalan[i] = 0;`
`        ``for` `(``int` `j=0; j<i; j++)`
`            ``catalan[i] += catalan[j] * catalan[i-j-1];`
`    ``}`

`    ``// Return last entry`
`    ``return` `catalan[n];`
`}`

`// Returns count of ways to connect n points on a circle`
`// such that no two connecting lines cross each other and`
`// every point is connected with one other point.`
`unsigned ``long` `int` `countWays(unsigned ``long` `int` `n)`
`{`
`   ``// Throw error if n is odd`
`   ``if` `(n & 1)`
`   ``{`
`      ``cout << ``"Invalid"``;`
`      ``return` `0;`
`   ``}`

`   ``// Else return n/2'th Catalan number`
`   ``return` `catalanDP(n/2);`
`}`