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.
2
-
3$\begingroup$ 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. $\endgroup$– Boris BukhCommented Apr 7, 2012 at 9:07
-
$\begingroup$ Crossposted here: math.stackexchange.com/questions/129363/… $\endgroup$– cardinalCommented Apr 8, 2012 at 19:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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?
-
1$\begingroup$ There is the situation where you have more than 3 points that are closest. Even so, I think your idea can be turned into a solid upper bound once you make clear that the 3 defining points are also inside the disk, and not just near the disk boundary. Gerhard "Ask Me About System Design" Paseman, 2012.04.08 $\endgroup$ Commented Apr 8, 2012 at 17:33