Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 disks containing at least $k$ points for some $k$, two discs are equivalent if they contain the same points.

I have some intuition here, but I'm not sure if I should follow it.

the number of distinct open discs containing at least $k$ points, for $k>2$ is bounded by ${n\choose 3}$, since every disk is uniquely defined by the 3 points closed to its boundary. Every 3 points form a triangle bounded by some disk. Suppose two different disks have the same 3 points being closest to the edge, than at least one disk has a point contained in it, which is not contained inside the other disc, than we can "shrink" the first disk until the "spare" point is closest to its edge, then it is defined by a different triplet.

Is there any flaw in my thinking?

share|cite|improve this question
@A.Schulz: Both spellings disc and disk are correct. – t.b. Sep 14 '12 at 12:44

Your argument could do with clearer terminology and presentation. At any rate something is wrong, at least in the specifics for smallish $n$ and $k = 3$.

Letting $n = 4$ and arranging points as in a square, there are $5$ different subsets of points of size three or more that can be realized (segregated by open disks): all four points together with the four subsets of size three. But $\binom{4}{3} = 4$.

Letting $n = 5$ and arranging points as in a regular pentagon, there are $11$ different subsets of points of size three or more that can be realized: all five points, the five subsets of size four, and five subsets of size three that exclude a consecutive pair of points. But $\binom{5}{3} = 10$. [Indeed by "pinching" the regular pentagon slightly, we could fit an additional subset of three into an open disk.]

Perhaps meditating on these small examples will help you to sharpen your insight. Note that the problem includes the parameter "at least $k$ points, for $k \gt 2$" but the proposed upper bound $\binom{n}{3}$ does not depend on $k$. In that case the requirement would be as if $k = 3$ had been specified.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.