CODEWITHSUNDEEP
algorithmgeometrygraph-algorithm
acd3456
acd3456

Reputation: 105

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.

Upvotes: 0

Views: 299

Answers (2)

wcochran
wcochran

Reputation: 10896

Note that any 4 points on a circle form a quadrilateral (choose them in cw order for example). You just need to find all integral values that are pythogorean triples where m^n + n^2 = r^2

T = 0
for m = 1 ... r
    for n = 1 ... r
        if m*m + n*n = r*r
            T++
N = 4*T  // (+/-m, +/-n) points on circle
result = N > 0 ? (N choose 4) : 0   // all quads

You can get rid of the inner loop above for efficiency sake (n^2 = floor(r^2 - m^2))

Upvotes: 0

ddfra
ddfra

Reputation: 2565

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

Upvotes: 2

Related Questions