Counting number of quadrilaterals that can be made with a set of points on a circle

Let x^2 + y^2 = r^2 be a circle with r a real.

First I get all integer points that are on the circle (e.g. (1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1) for r=sqrt{5})

How can I get the number of quadrilaterals that are possible on with theses points ?

The only way I know is to brute force and test all possible 4-cycles and remove ones with crossing edges but it become too much large for big r. Even for r=sqrt(5) it take about 10 seconds with python.

Solution

Change approach, start from a simple problem:

Given a set of poins that lie on a circle:

How many quadrilaterals can you have if the size is 3?
- Easy: 0
How many quadrilaterals can you have if the size is 4?
- Since the points lie on the same circle you will never have 3 points lying on the same straight line. So the answer is 1

now it becomes a bit harder

How many quadrilaterals can you have if the size is 5?
- For 4 points we have just one quadrilateral: (p1, p2, p3, p4). Now I can replace each one of them with p5. The total is 5.
How many quadrilaterals can you have if the size is n?
- You can have as many quadrilaterals as the number of possible combinations without repetitions of a set of n items in subsets of size 4, which is n!/(4!*(n-4)!)

you don't need to know what coordinates have the points, but just how many are them. Remember: Given 3 points which don't lie on the same straight line you can have only one circle. How ever you get three points from a circle they will never lie one the same straight line. This means that how ever you get 4 points from a circle you can use them to build a quadrilateral