Here is a random distribution of points on a $12\cdot 12$ grid illustrating Demaine neighbors (as you can see, it can happen that a horizontal or vertical has no points at all - that doesn't cause issues):
Two points are Demaine neighbors (=arborally unsatisfied) iff their (axis-parallel) rectangle is otherwise empty and has nonzero area. (Shown by connection.) As you can also see, some points have no Demaine neighbors, which is neither an issue.
Here is a plot of the number of Demaine neighbors totalled up over $100$ random runs respectively, on a $n\cdot n$ grid ($n=20$), with the point density $0\le d\le 1$ varying in $1\%$-steps.
It is obvious that $0$ points have no Demaine neighbors, but neither have $n\cdot n$! So, an optimal density $d$ must exist (maybe somewhat dependent on $n$).
Can you compute or at least estimate $d(n)$? In the plot $d\approx 0.26$. If $n=100$, $d\approx 0.23$, for $n=500$, $d\approx 0.24$, and then my program will take hours, but it seems to converge. ($d=1/4$ would be too good to be true...)
