A randomized version of straight-edge and compass construction Suppose you start with two points in the plane which are distance 1 apart, which for concreteness can be $(0,0)$ and $(0,1)$. Then you keep marking new points based on ruler and compass constructions. That is, you start with those two points as "marked. " At each stage you draw all possible circles which have a previously marked point as a center and with another previously marked point as a point on the circle, and you draw every line which goes through any two marked points. Then you mark every point which is an intersection of a circle or line and a circle or line. The set of marked points is the set of "constructible" points and has been studied since the ancient Greeks.
Here is a variant of that. Instead what happens if at each stage instead of throwing in every new line and circle, we only throw in those from a single pair of points chosen randomly and uniformly from all currently marked points? That is, suppose that at each stage we pick two marked points chosen uniformly at random, and we throw in the line and two circles determined by those points, and then mark every new point resulting from those circles and lines intersecting with each other or our existing circles and lines.
Question: With probability 1 do we still end up with all constructible points in our resulting set?
This seems hard. I don't even see any obvious way to prove that with probability 1 our resulting set is dense in the plane (which is trivially true for the set of constructible points).  Based on the answer to [this question], one can choose specific points to get very far away from the origin very fast but there one is carefully choosing specific points.
 A: Fleshing out my comment slightly, here's a heuristic argument with a couple of blanks to be filled in that suggests that most points will be 'found' with probability $\lt 1$. For approximation purposes I'm going to ignore logarithmic factors here, so take all $O()$, etc. as being 'up to $n^{o(1)}$ factors'.
The argument is straightforward: pick some $P$ not in the initial assembly (e.g., $P=(0, 100)$.) Suppose that the asymptotic number of points in the construction after $n$ stages is $\Theta(n^\alpha)$ for some $1\leq \alpha \leq 2$. Then we have $\Theta(n^{2\alpha})$ pairs of points to choose; further suppose that $\Theta(n^\beta)$ of those pairs add the point $P$. Then at each iteration, $P$ gets added with probability $\Theta(n^{\beta-2\alpha})$ and therefore never gets added at all with probability $\prod_n\left(1-\Theta(n^{\beta-2\alpha})\right)$; if we have $\beta\lt2\alpha-1$ then this product converges to a non-zero value.
From a different angle, note that if the asymptotic size is $\Theta(n^\alpha)$ then at each stage $\Theta(n^{\alpha-1})$ points are added. If there are $\Theta(n^\gamma)$ 'new' points accessible from the construction at stage $n$ and we assume that each point is added with equal probability, then any given accessible point will be added with probability $\Theta(n^{-(1+(\gamma-\alpha))})$; in particular, if it can be shown that the number of points immediately constructible from a figure of size $n^\alpha$ is $\Omega(n^{\alpha+\epsilon})$ for some $\epsilon\gt 0$ then we get the same convergence result. This seems likely to me if $\alpha\gt 1$, but of course filling in the blanks here is bound to be highly non-trivial.
