Editing Alignments of random points (section)

== Estimate of probability of chance alignments ==
Contrary to intuition, finding alignments between randomly placed points on a landscape gets progressively easier as the geographic area to be considered increases. One way of understanding this phenomenon is to see that the increase in the number of possible [[combination]]s of sets of points in that area overwhelms the decrease in the probability that any given set of points in that area line up.

One definition which expresses the generally accepted meaning of "alignment" is:
{{quote|A set of points, chosen from a given set of landmark points, all of which lie within at least one straight path of a given width}}

More precisely, a path of width ''w'' may be defined as the set of all points within a distance of ''w/2'' of a [[straight line]] on a plane, or a [[great circle]] on a sphere, or in general any [[geodesic]] on any other kind of [[manifold]].  Note that, in general, any given set of points that are aligned in this way will contain a large number of infinitesimally different straight paths.  Therefore, only the existence of at least one straight path is necessary to determine whether a set of points is an alignment. For this reason, it is easier to count the sets of points, rather than the paths themselves. The number of alignments found is very sensitive to the allowed width ''w'', increasing approximately proportionately to ''w''<sup>''k''−2</sup>, where ''k'' is the number of points in an alignment.

The following is a very approximate order-of-magnitude estimate of the likelihood of alignments, assuming a plane covered with uniformly distributed "significant" points.

Consider a set of ''n'' points in a compact area with approximate diameter ''L'' and area approximately ''L''<sup>2</sup>. Consider a valid line to be one where every point is within distance ''w''/2 of the line (that is, lies on a track of width ''w'', where ''w'' ≪ ''L'').

Consider all the unordered sets of ''k'' points from the ''n'' points, of which there are:

:<math>\binom nk = \frac {n!} {(n-k)!\,k!}</math>

(see [[factorial]] and [[binomial coefficient]] for notation).

To make a rough estimate of the probability that any given subset of ''k'' points is approximately [[collinearity|collinear]] in the way defined above, consider the line between the "leftmost" and "rightmost" two points in that subset (for some arbitrary left/right axis: the top and bottom can be chosen for the exceptional vertical case). A straight line can trivially be drawn through those two points. For each of the remaining ''k''-2 points in the subset, the probability that the point is "near enough" to the line is roughly ''w''/''L'', which can be seen by considering the ratio of the area of the line tolerance zone (roughly ''wL'') and the overall area (roughly ''L''<sup>2</sup>).

So, based on the approximate estimates above, the expected number of k-point alignments in the overall set can be estimated to be very roughly equal to

:<math> \frac {n!} {(n-k)!\,k!} \left(\frac{w}{L}\right)^{k-2}</math>

Among other things this can be used to show that, contrary to intuition, the number of ''k''-point lines expected from random chance in a plane covered with points at a given density, for a given line width, increases much more than linearly with the size of the area considered, since the [[combinatorial explosion]] of growth in the number of possible combinations of points more than makes up for the increase in difficulty of any given combination lining up.