# upper bound for the number of open discs containing k points in the plane

Hello,

I hope that you can help me with this.

Let P be a set of points in the plane, such that |p|=n, what is the maximal number of open discs containing atleast k points for some k, two discs are equivalent if they contain the same points.

• At very least you need to know how many points of $P$ are in the set. Say there are $n$ of them. Then you can get an upper bound that is polynomial in $n$. The keyword here is "VC dimension". There is a freely available Chazelle at cs.princeton.edu/~chazelle/book.html where one can find a good exposition. Apr 7 '12 at 9:07
• Crossposted here: math.stackexchange.com/questions/129363/… Apr 8 '12 at 19:54

Hmm, i think i have an idea, the number of distinct open discs containg atleast k points, for k>2 is bounded by ${n \choose 3}$, since every disc is uniquely defined by the 3 points contained in it and closest to its boundry. every 3 points form a triangle bounded by some disc. suppose two diffrent discs have the same 3 points being closest to the edge, than atleast one disc has a point contained in it, which is not contained inside the other disc, than we can "shrink" the first disc untill the "spare" point is closest to its edge, then it is defined by a diffrent triplet. is there any flaw in my thinking?