13
$\begingroup$

Whenever I draw randomly about ten points, I see that there will be always 3 points that are "almost" collinear. This observation leads me to considering the following questions:

Question 1: Suppose $n$ points are generated uniformly randomly in a square, let $\phi_n$ be the largest angle that is formed by three of them. How quickly does $E(\phi_n)$ tend to $\pi$?

Question 2: For $n>2$ and $\epsilon > 0$, estimate $P(\phi_n > \pi-\epsilon)$?

$\endgroup$
1
  • 4
    $\begingroup$ My guess: $\pi - E(\phi_n)$ should decay as $\Theta(1/n^3)$, as this is the number of triplets, there are few dependencies and the distribution of the angle in a given triplet is not far from uniform. $\endgroup$ Commented Aug 11, 2016 at 12:11

4 Answers 4

4
$\begingroup$

The intuition in the comment by Ori Gurel-Gurevich appears to be correct. Indeed, let us show that $\pi-\phi_n$ is on the order of $1/n^3$ in probability.

Let $T$ denote the set of all triangles with vertices at some of the $n$ points, with $N:=|T|=\binom n3$, the cardinality of $T$. For each $t\in T$, let $X_t$ denote the largest angle in the triangle $t$, so that $\phi_n=\max_t X_t$. It should be not hard to show that (i) the random variable (r.v.) $X_t$ has a density $f$ left-continuous at point $\pi$, with $f(\pi-)=:c\in(0,\infty)$ and (ii) for any distinct $t$ and $s$ in $T$, the random pair $(X_t,X_s)$ has a joint density bounded by some $C<\infty$.

Now we can use the key result by Galambos \url{https://www.jstor.org/stable/2239989?seq=1#page_scan_tab_contents}, based on a combinatorial graph sieve theorem by Renyi, with $N$ in place of the symbol $n$ in that paper, and with $E$ defined as the set of pairs $(t,s)\in T^2$ such that the triangles $t$ and $s$ have at least one common vertex. Then clearly $N_E:=|E|=O(n^3\cdot n^2)=o(N^2)$.

For any fixed positive real $a$, let $c_N=c_N(a)$ be the root of the equation $$NP(X_t>c_N)=a.$$ Since $P(X_t>x_N)\sim c(\pi-x_N)$ if $x_N\uparrow\pi$, we have
\begin{equation} c_N=\pi-\frac{a}{cN}\,(1+o(1)); \end{equation} all the limit relations here are for $n\to\infty$. Then it is easy to see all the conditions in Galambos's theorem hold, with $r(\dots)=0$ in his condition (iii) and $d_k=1$ in his condition (iv). It follows that $P(\phi_n<c_N)\to e^{-a}$, which is equivalent to \begin{equation} P(cN(\pi-\phi_n)>a)\to e^{-a}, \end{equation} for each real $a>0$. That is, the r.v. $\frac c{3!}\,n^3(\pi-\phi_n)$ converges to an exponential r.v. in distribution.

Additional efforts are needed to show that the corresponding convergence of the means holds, so that $\frac c{3!}\,n^3\mathbb{E}(\pi-\phi_n)\to1$, whence $\mathbb{E}(\pi-\phi_n)\sim\frac{3!}c\,n^{-3}$.

$\endgroup$
2
  • 2
    $\begingroup$ A more general result, with the square replaced by an arbitrary bounded convex subset of $\mathbb{R}^d$ with nonempty interior, where $d\ge2$, is now presented, with complete details, in \url{dropbox.com/s/hqmb33qqs9j7khg/2.pdf?dl=0}. $\endgroup$ Commented Aug 16, 2016 at 1:01
  • 1
    $\begingroup$ Now a better presentation is available at arxiv.org/abs/1608.04455 . $\endgroup$ Commented Aug 22, 2016 at 14:29
2
$\begingroup$

Concerning Question 2, $P(\phi_n > \pi-\epsilon)$ is at least exponentially close to $1$. Indeed, let $(p_1,\dots,p_n)$ be the random sequence of $n$ points drawn independently and uniformly from the square. Let $k:=\lfloor n/3\rfloor$. For $j=1,\dots,k$, let $A_j$ denote the largest angle in the triangle with vertices $p_{3(j-1)+1},p_{3(j-1)+2},p_{3(j-1)+3}$. Then $\phi_n\ge A_1\vee\cdots\vee A_k$, and so, \begin{equation} P(\phi_n > \pi-\epsilon)\ge1-P(A_1\vee\cdots\vee A_k \le \pi-\epsilon) =1-q^k=1-q^{\lfloor n/3\rfloor}, \end{equation} where $q:=P(A_1\le\pi-\epsilon)<1$.

$\endgroup$
2
  • $\begingroup$ You should have got $1-(1-q)^k$ rather than $1- q^k$ $\endgroup$
    – S.B.
    Commented Aug 10, 2016 at 17:49
  • $\begingroup$ I have fixed the typo. $\endgroup$ Commented Aug 10, 2016 at 18:48
2
$\begingroup$

On question 2, if $n > 2\pi/\epsilon$, then $P(\phi_n > \pi-\epsilon) = 1$.

Arrange the points in a polygon. The total of the interior angles is $(n-2)\pi$, so at least one must be at least $\pi - 2\pi/n$.

$\endgroup$
2
  • 1
    $\begingroup$ If the points are chosen at random then usually they won't form a convex $n$-gon. Already for $n=4$ one point might be in the interior of the triangle formed by the other three. $\endgroup$ Commented Aug 11, 2016 at 6:04
  • 7
    $\begingroup$ However, it is known that for each $n$ there is some $N$ such that any $N$ points in the plane, no three collinear, include the vertices of a convex $n$-gon. (This is a clever application of Ramsey's theorem cut-the-knot.org/arithmetic/combinatorics/PolygonalRamsey.shtml .) Your argument then proves that $P(\phi_N > \pi - \epsilon) = 1$. $\endgroup$ Commented Aug 11, 2016 at 6:09
1
$\begingroup$

This is not an answer to your original specific question, but this recent related result (and its references) may help:

"Finding Points in General Position." Vincent Froese, Iyad Kanj, André Nichterlein, Rolf Niedermeier. May 2016. arXiv abstract.

"Given a set of points in the plane, find a maximum-cardinality subset of points in general position. We prove that [this problem] is NP-hard, APX-hard, and present several fixed-parameter tractability results for the problem."

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .