n > 3. S = {P1, ... , Pn} is a set of n points in the plane, no three collinear and no four concyclic. Let ai be the number of circles through three points of S which have Pi as an interior point. Let m(S) = a1 + ... + an. Show that the points of S are the vertices of a convex polygon iff m(S) = f(n), where f(n) is a value that depends only on n.
Solution
Answer: f(n) = 2 n(n-1)(n-2)(n-3)/4!
Consider first the case n = 4. If the convex hull is a triangle, then m(S) = 1. Suppose ABCD is convex. Without loss of generality angle ABD > angle ACD. So B lies inside the circle ACD and C lies outside the circle ABD. Hence A lies outside the circle CBD. Hence D lies inside the circle ABC. So m(S) = 2.
Now consider n > 4 points. Suppose there are c(S) convex subsets of 4 points. Each of those gives 2 circles through 3 points with 1 inside. The other nC4 (binomial n!/( (n-4)! 4!) - c(S) subsets of 4 points give just one such circle. So m(S) = c(S) + nC4. Now put f(n) = 2 (nC4). If m(S) = f(n), the c(S) = nC4, so every subset of 4 points is convex, so S is convex. Conversely, if S is convex, then c(S) = nC4, so m(S) = f(n).
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 2002