# Orchard-planting problem in space

The original orchard-planting problem asks for the maximum number of $3$-point lines attainable by a configuration of points in the plane. I am interested in its natural generalization for (three-dimensional) space, that is in the maximum number of $4$-point planes attainable by a configuration of points in the space, no $3$ of which are collinear and no $5$ of which are coplanar. I guess this should be a known problem, but, surprisingly, I googled nothing about it.

More precisely, I am interested only in an upper bound of this number and shall be quite happy if it is $o(n^2)$. In fact, if it is $c n^2$ for $c<1/12$ then we already obtain an improvement over a straightforward asymptotic lower bound for the minimal number $\rho(n)$ of planes in space needed to a straight-line crossing free drawing of the complete graph $K_n$ in Theorem 12 from our paper "Drawing Graphs on Few Lines and Few Planes". For instance, $\rho(6)=4$, that is for $K_6$ we need exactly $4$ planes.

Thanks.

PS. This approach to the lower bound for our problem failed, because for it are essential only planes containing fours of points in a non-convex position, but it is too specific to ask for a reference.

• $c < \frac{1}{12}$ shouldn't be attainable; take $n$ divisible by 3, and divide it into 3-point sets. Make each of those 3-point sets collinear but otherwise put the points in general position; for each choice of a 3-point set and a point outside it, you get a 4-point plane, which gives $\frac{n}{3} (n - 3)$. So you may want to instead assume something about collinearity? – user44191 Dec 1 '16 at 6:53
• @user44191 Thanks, indeed, in my application I have that no $3$ points are collinear. – Alex Ravsky Dec 1 '16 at 10:01
• Take $n/2$ lines passing through one point, and take two points on each line. You may do this so that your conditions are satisfied. This way you get around $(n/2)^2/2=n^2/8$ 4-points planes... – Ilya Bogdanov Dec 1 '16 at 10:12

Assume $n$ is even. Take $n/2$ lines passing through one point, and take two points on each line. You may do this so that your conditions are satisfied. This way you get around $(n/2)^2/2=n^2/8$ 4-points planes (and you may also get some extra ones!), so $c\geq 1/8$.

[ADDENDUM] Let me address the non-convex case mentioned in the update of the post.

Start a similar construction, but work inductively. On the first step, take 4 coplanar points in a non-convex position.

Assume that we have constructed $n$ points at some step. Now take a generic point $A$ and draw $n$ lines through these points. On a half of these lines, we choose a second point on the same side of $A$ (tha the already present one), on the remaining lines --- a second point on a different side of $A$. Thus we pass from $n$ to $2n$ points and increase the number of "non-convex planes" by $(n/2)^2=n^2/4$.

So, if we had $c_nn^2$ non-convex planes, then we get $(c_n/4+1/16)(2n)^2$ of them in a new arrangement, i.e., $c_{2n}=c_n/4+1/16$. The sequence $c_4,c_8,c_{16},\dots$ converges to the solution of $c=c/4+1/16$, i.e., to $c=1/12$. Thus it seems that there is no hope even in this case...

I'm completely not sure, but it seems that we may also add some extra non-convex planes passing through the added points. But we need to be careful in order not to add some forbidden collinearities or coplanarities...

• Well, if you need only non-convex configurations, this construction provides only around $n^2/16$ planes... – Ilya Bogdanov Dec 1 '16 at 10:50
• I've added some thoughts on the non-convex case. – Ilya Bogdanov Dec 2 '16 at 8:54