30
$\begingroup$

I uniformly mark $n^2$ points in $[0,1]^2$. Then I want to draw $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. Surely, for a given constant c it is not always possible.

But it seems that for $c=100$ when n tends to infinity, the probability that such a cut exists should tend to one, as a variation of the law of the large numbers. Do you have any idea how to prove this rigorously?

$\endgroup$
5
  • $\begingroup$ What's you heuristics for the suggestion that the probability goes to one? As a side comment, there are results describing the asymptotics of the side of the largest empty square with sides parallel to those of [0,1]^2. A version of rectangles instead of squares also exist, I think. The proof is, however, is not a LLN-type one. $\endgroup$ Jun 9, 2020 at 11:42
  • $\begingroup$ @Vysotsky not a heuristics, but a somewhat weaker statements can be observed experimentally and it would follow from the positive answer to my question. The statement is that the degree of a tropical curve through n^2 random points in a square is concentrated near n. $\endgroup$ Jun 9, 2020 at 11:58
  • $\begingroup$ @Vysotsky note also that we cut AFTER we marked points randomly, so there is more freedom. $\endgroup$ Jun 9, 2020 at 13:53
  • $\begingroup$ @Nikita Kalinin Of course, this is the main point (and difficulty)! Otherwise the claim will not work, as per the answer attempts below. It is unclear to me why your problem should in a sense correspond to some law of large numbers. $\endgroup$ Jun 9, 2020 at 14:03
  • $\begingroup$ @Nikita Kalinin It is a nice problem! But somehow I share Iosif Pinelis's scepticism that cn would not suffice. You do have a reasonably quick algorithm how to compute the cuts for a given realisation of points, do not you? $\endgroup$ Jun 9, 2020 at 14:54

8 Answers 8

26
$\begingroup$

Given $n^2$ i.i.d. uniform points in $[0,1]^2$, the goal is to draw a configuration of $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point.

We show below that $c$ must satisfy $c=\Omega(n^{1/3})$ for this to be typically possible:

In fact, $\Theta(n^{4/3})$ lines are necessary and sufficient for such a configuration to exist with substantial probability.

More precisely, denote by $p_n(k)$ the probability that a configuration of $k$ vertical lines and $k$ horizontal lines separate $n^2$ i.i.d. uniform points $\{x_j\}_{j=1}^{n^2}$ in $[0,1]^2$.

Claim: For suitable constants $0<c_1<c_2<\infty$, we have (omitting integer part symbols):

(a) $\; p_n(c_1 n^{4/3}) \to 0$ as $n \to \infty$, and

(b) $\; p_n(c_2 n^{4/3}) \to 1$ as $n \to \infty$.

This is proved below with $c_1=1/20$ and $c_2=3/2$; no attempt has been made to optimize these constants.

Proof: Consider an auxiliary grid of $L:=n^{4/3}$ uniformly spaced vertical lines and $L$ uniformly spaced horizontal lines in the unit square. This grid defines $L^2$ grid squares of side length $1/L$.

(a) Call a grid square $Q$ nice if it contains exactly two of the $n^2$ given points $\{x_j\}$. Observe that for two distinct grid squares, the events that they are nice are negatively correlated. Call a nice grid square $Q$ good if there is at most one other nice square in its row and at most one other nice square in its column. The probability that a specific grid square $Q$ is nice is $${n^2 \choose 2}L^{-4}(1-L^{-2})^{n^2-2}=(1/2+o(1))L^{-1}.$$
Given that $Q$ is nice, The conditional expectation of the number of nice squares (other than $Q$) in the row of $Q$ is $1/2+o(1)$ Thus, given that $Q$ is nice, Markov's inequality implies that the conditional probability that there are two or more additional nice squares in the row of $Q$ (besides $Q$ itself) is at most $1/4+o(1)$. The same applies to the column of $Q$, and we deduce that $$P(Q \; {\rm is \; good}\; | Q \; {\rm is \; nice}) \ge 1/2+o(1) \, ,$$ so $$P(Q \; {\rm is \; good} ) \ge (1/4+o(1))L^{-1} \, .$$ Let $G$ denote the number of good grid squares. Then the mean satisfies $$E(G) \ge (1/4+o(1))L \,.$$ Observe that if we replace one point $x_i$ by $x_i'$ then $G$ will change by at most 5, so Mcdiarmid's inequality, see [1, Theorem 3.1] or [2], implies that for $n$ large enough, $$P(G \le L/5) \le \exp(-\frac{(L/21)^2}{25n^2}) \to 0 \,. {\rm as} \; n \to \infty \,.$$ (Alternatively, one could invoke the Efron-Stein inequality or estimate the variance directly to verify this.) Now suppose that $S$ is a set of vertical and horizontal lines that separate the points $\{x_j\}_{j=1}^{n^2}$. For each good grid square $Q$, a line of $S$ is required to separate the two points $x_i, x_j$ in the square, and each such line can be used for at most two good squares. Thus $|S| \ge G/2$ so $$p_n(L/20) \le P(\exists \; {\rm separating } \; S \; {\rm with } \; |S| \le L/10) \le P(G \le L/5) \to 0 $$.

(b) Denote by $M$ the number of pairs $(i,j)$ such that $1 \le i<j \le n^2$ and $x_i,x_j$ fall in the same grid square. Then $E(M) = {n^2 \choose 2}L^{-2} \le L/2$, and another application of McDirarmid's inequality implies that $P(M \ge L) \to 0$ as $n \to \infty$.

Finally, construct a separating set of lines $S$ by combining the $2L$ lines of the auxiliary grid with one separating line for each pair $(i,j)$ counted in $M$ (we can take half of these lines vertical and half horizontal). Then $P(|S| \ge 3L) \to 1$ as $n \to \infty$ and $p_n(3L/2) \to 1$ as well.

[1] McDiarmid, Colin. "Concentration." In Probabilistic methods for algorithmic discrete mathematics, pp. 195-248. Springer, Berlin, Heidelberg, 1998.http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8B1FFFE4553B63543AFEA0706E686E65?doi=10.1.1.168.5794&rep=rep1&type=pdf

[2] McDiarmid, C. (1989). "On the method of bounded differences". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148–188. MR 1036755

$\endgroup$
3
  • $\begingroup$ Do you think the constant $k$ for which $p_n(k·n^{4/3}) → r ∈ (0,1)$ as $n→∞$ is rational or irrational? And what do you think it is? $\endgroup$
    – user21820
    Jun 10, 2020 at 9:07
  • $\begingroup$ Very nice proof. I initially read the question wrong, and thought the grid was assumed uniform. But rather it can be actively chosen. A couple of points that I had to struggle with: the first estimate can be seen by realizing the binomial factor is 1 + o(1). For the constant 5, note removing a point can promote at most 4 grids to being good (2 on the same row and 2 on the same column), and adding a point can promote at most 1 grid, namely the grid where the point lands. Lastly for part b, two points are not on the same x or y cord with probably 1. How likely is it to get sharp estimate for c? $\endgroup$
    – John Jiang
    Jun 17, 2020 at 13:56
  • $\begingroup$ A similar reasoning with the bound of $n^{4/3}$ also appears in the paper 'On Separating Points by Lines' by Har-Peled and Jones $\endgroup$ Jun 20, 2020 at 19:17
12
$\begingroup$

Interestingly, if we allow the lines to have arbitrary directions, it still requires roughly n^{4/3} (up to a log correction) lines to separate all the points.

https://www.cambridge.org/core/journals/proceedings-of-the-london-mathematical-society/article/economical-covers-with-geometric-applications/486374A93F4351DF26C155F6C3FE35AE

$\endgroup$
1
  • 1
    $\begingroup$ That is beautiful. Thanks for the reference! $\endgroup$ Jun 10, 2020 at 14:06
8
$\begingroup$

Label your $N$ points as $(x_i,y_{\sigma(i)})$ with $x_1 < \cdots < x_N$ and $y_1 < \cdots < y_N$ ; this defines a uniform random permutation $\sigma \in \mathfrak{S}_N$, and all the information about the problem is encoded in $\sigma$.

Let $C$ be the number of axis-parallel cuts needed to scatter all the points. An easy lower bound is $C \geq L-1$, where $L$ is the length of the longest monotone subsequence of $\sigma$. It is well known that $L \sim 2 \sqrt{N}$ in probability, so if we could show that the above lower bound is typically sharp, this would solve the problem.

$\endgroup$
7
  • $\begingroup$ Interesting! Could you comment on how to find the cuts based on the permutation? $\endgroup$
    – S.Surace
    Jun 9, 2020 at 17:16
  • 1
    $\begingroup$ This is an interesting connection. However, I am afraid that the longest monotone subsequence will account only for a rather small subset of the set of $n^2$ uniformly chosen points in the square. $\endgroup$ Jun 9, 2020 at 17:35
  • $\begingroup$ The idea is that maybe some of the techniques used for longest increasing subsequence can apply here. If the answer to the OP is positive, it implies that the longest increasing subsequence is $O(\sqrt{N})$, which is not a trivial fact. Also, I'd like to see a permutation with $C \gg L$. $\endgroup$ Jun 9, 2020 at 17:43
  • $\begingroup$ @S.Surace I don't undestand the question. I don't know how to find the cuts, this is just a lower bound. $\endgroup$ Jun 9, 2020 at 17:44
  • 1
    $\begingroup$ Here is an example with $C \gg L$. Split $\{1,\dots,N\}$ into $\sqrt{N}$ blocks (=intervals) of size $\sqrt{N}$ and let $\sigma$ be the permutation which reverses the order inside each block. Then $L=\sqrt{N}$ and $C \geq \sqrt{N}(\sqrt{N}-1)$, since a cut can only scatter within one block, and each block requires $\sqrt{N}-1$ cuts to be scattered. $\endgroup$ Jun 9, 2020 at 20:41
6
$\begingroup$

This is to show rigorously that the uniform rectangular grid does not work -- cf. the answer by mike. As in the answer by Dieter Kadelka, suppose that the $cn$ vertical lines and the $cn$ horizontal lines partition the unit square into $$N:=(cn+1)^2$$ small squares of equal area $1/N$, where $c\ge1$. Let $$K:=n^2.$$ Then the probability that each small square contains at most one random point is \begin{aligned} \frac{N(N-1)\cdots(N-K+1)}{N^K}&=\Big(1-\frac1N\Big)\cdots\Big(1-\frac{K-1}N\Big) \\ &<\exp\Big\{-\sum_{k=1}^{K-1}\frac kN\Big\} \\ &=\exp\Big\{-\frac{(K-1)K}{2N}\Big\}\to0\ne1 \end{aligned} as $n\to\infty$, as claimed.

(I don't think any choice -- even a random one, depending on the random points -- of $cn$ lines in both the vertical and horizontal directions is enough, for any real $c>0$. I think, instead of $cn$, one needs at least something like $n\ln^a n$ for some real $a>0$.)

$\endgroup$
5
  • $\begingroup$ I think there remains the possibility that the grid is chosen dependent on the $n^2$ random points, but I would not bet on this. $\endgroup$ Jun 9, 2020 at 14:26
  • $\begingroup$ @DieterKadelka : Yes, the very fast convergence to $0$ (rather than $1$) for the uniform grid strongly suggests that even a $cn\times cn$ grid dependent on the $n^2$ random points will not be enough. $\endgroup$ Jun 9, 2020 at 14:35
  • 6
    $\begingroup$ yes, sure, that is why I wrote that we mark points and only then we draw lines... $\endgroup$ Jun 9, 2020 at 14:40
  • 1
    $\begingroup$ @Nikita Kalinin: Do you have an algorithm to do this effectively? $\endgroup$ Jun 9, 2020 at 15:15
  • 1
    $\begingroup$ @DieterKadelka : If I were going to try to make such an algorithm (which I am not, have no interest in doing, and refuse to even think through enough details to see if it could plausibly be made to work), I would start with a partitioning $k$-d tree having the defect that non-root interior nodes partition the entire space, not just the space associated with their parent. Depth control of that tree might give a useful bound on the number of partitioning lines. $\endgroup$ Jun 10, 2020 at 2:02
4
$\begingroup$

If we draw the horizontal lines to have $p$ rows with $n^2/p$ points each, then finding where to put the vertical lines becomes a birthday problem : we take the points from left to right and find in wich row they belong. When the row is already taken, we must draw a vertical line and start a new column. Set $X_i$ the number of points in column $i$. The repartition function of $X_1$ converges to $\exp(-x^2/p)$.

If we can suitably control the law of the other $X_i$, this would give an order of $n^2/\sqrt{p}$ columns. For $p\sim n^{4/3}$, this means around $n^{4/3}$ columns.

This provides as upper bound an order of $n^{4/3}$ horizontal lines and vertical lines. If some form of concentration occur for the size of the columns, we would get a critical value at $c_{crit}n^{4/3}$, with proba 1 of having a solution for constants larger than $c_{crit}$.

$\endgroup$
1
  • $\begingroup$ To control $X_i$ (so that the columns are big enough in law), note that while there are still enough points, we can use modified birthday problems to find lower bounds in law on the size of the colums. For the right-most columns, just start again from the right. Set $(Y_i)_{1\leq i\leq N}$ the size of each column (starting from the right). $Y_i$ is distributed as $X_i$, and there is a relation between the columns from the left and from the right (the bounds of a column from the right should be in two adjacent columns from the left, and vice-versa). So, a column is always of order $\sqrt p$. $\endgroup$ Jun 9, 2020 at 23:34
3
$\begingroup$

Nikita Kalinin, you were right, this problem indeed reduces to a rather general form of the law of large numbers, namely subadditive ergodic theorem! This theorem is used, e.g., to prove the result on the length of the largest increasing subsequence mentioned by Guillaume Aubrun (thanks for hinting the direction). So I just mimic its proof due to Hammersley (see, e.g. Example 7.5.2 in Durrett's "Probability: Theory and Examples").

First of all, as noted above, instead of the original setting with $n^2$ points in $[0,1]^2$ we can consider your question for a Poisson point process (PPP) of unit intensity on the positive quadrant restricted to $[0,n]^2$.

For any integer $0 \le m <n$, let $C_{m,n}$ be the minimal positive integer number such that it is possible to cut the rectangle $[[m,n]]:=\{(x,y) \in [0, \infty)^2: m \le x, y \le n\}$ with the points of the PPP using $C_{m,n}$ horizontal and $C_{m,n}$ vertical cuts to satisfy the condition. The key observation is that $$C_{0,m} + C_{m, n} \le C_{0,n}.$$ Indeed, just use optimal cuts to cut $[[0,m]]$ and $[[m,n]]$; then more cuts may be needed.

By the subadditive ergodic theorem, $$\lim_{n \to \infty}\frac{C_{0,n}}{n} = \sup_{n \ge 1} \frac{E C_{0,n}}{n}:=c, \qquad a.s.$$

Now the problem is to figure out whether $c$ is finite or not, which is the most interesting bit. I did not succeed so far.

One way to prove finiteness is to show that $E C_{0, n+1} - E C_{0,n}$ is bounded. This appears to be wrong on a first sight, but apparently this is not so trivial. On the other hand, finiteness would mean that cutting $[[0,n]]$ and $[[n, 2n]]$ in a nearly optimal way would automatically fix the two remaining subsquares of $[[0,2n]]$. This should not be true, but not simple to prove as well.

The last comments are that the same argument goes through if replace $C_{m,n}$ by the total number of horizontal and vertical cuts. And the sequence $E C_{0,n}/n$ is strictly increasing.

$\endgroup$
2
$\begingroup$

Not and answer, but a long comment: I don't think a uniform rectangular grid works. Take a planar poisson process with intensity 1 and look at (0,n)x(0,n). This is your setup except I have replaced the uniforms with a poisson process with an expected n^2 events in the space. Divide it into a rectangular grid with (cn)^2 rectangles of area 1/c^2 each. The number of points in each rectangle is poisson with parameter 1/c^2,and different rectangles are independent. You wonder if any have of the (cn)^2 rectangles have two points in them. As the parameter is fixed there is a probability going to 1 that at least one of them does.

$\endgroup$
0
0
$\begingroup$

It is sufficient to assume that the $cn$ vertical and $cn$ horizontal lines are at $\frac{1}{cn}, \frac{2}{cn+1}, \ldots$, so that we have $N := (cn+1)^2$ small rectangles each with area $p^{(n)} := \frac{1}{N}$. Let $X_1,\ldots,X_N$ be random variables with $X_i$ the random number of points in rectangle $i$. Then $X := (X_1,\ldots,X_N)$ has the multinomial (sometimes called polynomial) distribution $\cal{M}(n; p^{(n)},\ldots,p^{(n)})$ ($N$ parameters $p^{(n)}$). As far as I understand your problem you want an estimation for $\mathbb{P}(X_1 \leq 1, \ldots, X_N \leq 1)$. But $q^{(n)} := 1 - \mathbb{P}(X_1 \leq 1, \ldots, X_N \leq 1) \leq \sum_{i=1}^N \mathbb{P}(X_i \geq 2)$, where each $X_i$ has Binomial distribution $Bin(n,p^{(n)})$. Thus $q^{(n)} \leq N \cdot \left(1 - (1 - p^{(n)})^n - n \cdot p^{(n)} \cdot (1 - p^{(n)})^{n-1}\right)$, which goes to $0$ when $c > 1$.

Edit: The estimation above only works for $n$ points, not for $n^2$ points, as required.

$\endgroup$
2
  • 1
    $\begingroup$ It looks like your bound on $q^{(n)}$ is $\sim1/(2c^2)\ne0$. $\endgroup$ Jun 9, 2020 at 12:54
  • 1
    $\begingroup$ Thank you @Iosif Pinelis, you are right. The estimation has to be sharpened (if it is possible). $\endgroup$ Jun 9, 2020 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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