4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ $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? $\endgroup$ – user44191 Dec 1 '16 at 6:53
  • $\begingroup$ @user44191 Thanks, indeed, in my application I have that no $3$ points are collinear. $\endgroup$ – Alex Ravsky Dec 1 '16 at 10:01
  • 2
    $\begingroup$ 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... $\endgroup$ – Ilya Bogdanov Dec 1 '16 at 10:12
5
$\begingroup$

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...

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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