4
$\begingroup$

Hello.

Looking at a set S of N points in the plane, I call a subset B of S "legal" if the set of points contained in the convex hull of B is exactly B itself. In other words, a subset B of S in legal if there exists some polygon P such that the set of points in and on P is exactly B.

Given N, can you bound from above the number of legal subsets of a set of N points in the plane?

Refinement: Given N, can you bound from above the number of legal subsets of size K of a set of N points in the plane?

Thank you very much.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Do you mean, B is legal if the set of points of S contained in the convex hull of B is B? In other words, $B = P \cap S$ for some convex set $P$. If we work in one dimension and let $S = \{1,2,3\}$, then if I understand, $\{1,2\}, \{2,3\}$ are legal subsets, but $\{1,3\}$ is not. $\endgroup$
    – Nate Eldredge
    Commented Jun 9, 2010 at 22:13
  • $\begingroup$ I guess one has really to consider N points in general position since the problem is to trivial otherwise. $\endgroup$
    – Roland Bacher
    Commented Jun 10, 2010 at 12:36

4 Answers 4

Reset to default
12
$\begingroup$

Why can't you just put the points in a circle? Doesn't that make all subsets legal?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Aww... this was so close to being an interesting problem- any chance we can do it on a finite lattice or something? $\endgroup$
    – Tom Boardman
    Commented Jun 10, 2010 at 7:20
  • $\begingroup$ I think "bound from above the number of legal subsets of a set of N points in the plane" refers to any set, that is, S is not considered as an object to be optimized. I think the questioner wants a statement like: "any set of N points possesses at least L legal subsets", with a sharp bound L. – Pietro Majer 43 secs ago $\endgroup$
    – Pietro Majer
    Commented Jun 10, 2010 at 8:24
  • $\begingroup$ I think 'bound from above' is all about finding an upper bound for L(N)- @gowers' answer shows that this is $2^n$. The lower bound you describe might be interesting too though... $\endgroup$
    – Tom Boardman
    Commented Jun 10, 2010 at 10:04
  • 1
    $\begingroup$ It's possible that Roland Bacher's comment on Tony Huynh's answer gives rise to an interesting problem (though I haven't thought about it yet so am not sure). $\endgroup$
    – gowers
    Commented Jun 10, 2010 at 13:19
  • $\begingroup$ Thanks. I'm a little embarrassed I missed that. Can you find an interesting condition on the points that makes the number of legal subsets be no more than polynomial in N? $\endgroup$
    – uuu
    Commented Jun 11, 2010 at 10:04
3
$\begingroup$

Here are a few thoughts about whether one can get a much better bound by imposing some natural condition on the set of points.

First, observe that the circle example generalizes to points in any convex (or concave) curve. This allows us to show that a random (in a suitable sense) set of points will give rise to a pretty large bound. For example, suppose we choose n points uniformly at random in the unit square. If we form an m-by-m grid of squares, where m is cn^{1/2} for some small positive constant c, then most of the squares in this grid will contain a point. With the help of that observation, one can obtain something like n^{1/4} points (I think) that lie on a convex curve. The way I'd do it is I'd pick a random circle of diameter 1/10 that lies in the square, argue that (on average) it intersects many squares of the grid that contain a point in the original set, and that we can pick a reasonably separate set of these squares. Since the squares have diameter m^{-1} or so, I think we need them to be at least m^{-1/2} apart for points in these squares to be in convex position: hence my suggestion of n^{1/4}.

So that suggests that a typical set of points will give rise to at least exp(cn^{1/4}) legal sets. I haven't checked whether it is easy to improve that bound.

This in turn suggests that the only way of getting a polynomial bound is to choose a rather peculiar set of points. The most obvious general idea for how to do that is some kind of inductive construction. For example, one could iterate the following procedure: given a finite set of points, replace each point by a tiny configuration that consists of the three vertices of a triangle plus a point in the interior of that triangle. Iterating that k times would give 4^k points. I don't know whether that particular construction gets one anywhere, but the thought behind it is to try as hard as possible to force triples of points to contain plenty of other points in their convex hull, or else to belong to small common triangles.

But that's more like a possible approach to constructing some points in general position that give rise to few legal sets rather than an interesting condition that would guarantee this. It seems to me because of the first argument that a set with only a few legal subsets would have to be extremely special and carefully constructed.

Improve this answer
$\endgroup$
2
$\begingroup$

For the lower bound, I am guessing that every set of N points in the plane contains at least N-1 legal subsets, with equality if and only if the points are in a line.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I think one has to add the condition that the points are in general position (three points are never aligned). Then the problem is less trivial. In this case, one can also ask for the number of "legal" triangles. (I think, the terminology "legal" is unfortunate, one should perhaps call legal sets "empty convex polygons", or something similar, describing the fact that these are points in convex position with convex hull containing no other points of $S$.) $\endgroup$
    – Roland Bacher
    Commented Jun 10, 2010 at 8:31
  • $\begingroup$ It seems that every set of N points in the plane contains at least 1 + N + N(N-1)/2 legal subsets (the empty sets, the singletons, and the line segments bounded by any two points, together with any other points that might happen to lie on the same line segment), with equality if and only if the points are in a line. $\endgroup$
    – David Eppstein
    Commented Jun 10, 2010 at 22:57
  • $\begingroup$ I regard a legal subset S, as one which contains at least 2 elements, and as Roland mentions S must be in convex position such that the conv(S) contains no other ponts of N. So, I do not consider the empty set nor singletons to be legal. Furthermore, a pair of points of N is not legal if there is another point of N between them. $\endgroup$
    – Tony Huynh
    Commented Jun 11, 2010 at 6:23
  • $\begingroup$ We're reading the problem differently then. It looked to me like a legal subset was any intersection of S with a convex set. He didn't say "vertices of the convex hull", he said "contained in the convex hull". $\endgroup$
    – David Eppstein
    Commented Jun 11, 2010 at 15:44
  • $\begingroup$ Yes, indeed we are. I believe that your interpretation of legal is actually the definition given by the OP. However, to me it seems kind of strange to be able to make an illegal set into a legal set by adding more elements to it. $\endgroup$
    – Tony Huynh
    Commented Jun 11, 2010 at 19:39
1
$\begingroup$

If I understand the question, you want the best (i.e. larger) constant $L_k(n)$ such that any set S of $n$ points in the plane (more generally, in a linear space V) always has at least $L_k(n)$ legal k-subsets. If so, I'd say that $L_k(n)=N-k+1.$ Indeed, if V is a line, we always have equality. In the general case, map linearly and injectively S onto a subset S' of a line. The image of an illegal k-subset of S is still an illegal k-subset of S', showing that there are at least as many legal k-sets in S as there are in S'. The total number is of course at least N(N+1)/2, with equality in dimension 1.

Improve this answer
$\endgroup$
1
  • $\begingroup$ and one more, if the empty set is to be considered as legal. $\endgroup$
    – Pietro Majer
    Commented Jun 10, 2010 at 8:28

You must log in to answer this question.