Connect the dots: how many random points can a regular curve pass through?

Ery Arias-Castro, David L. Donoho, Xiaoming Huo, Craig A. ToveyAdvances 2005 · DOI

Abstract

This paper provides a critical correction to the 2005 study "Connect the Dots," which investigated the maximum number of random points a regular curve can visit in a unit square. The authors identify and rectify a scaling error in their original theoretical asymptotic limit, shifting the constant from $2\sqrt{n}$ to $\sqrt{2n}$. This correction is supported by new computational experiments that resolve previous discrepancies in parameter labeling.

Introduction

In geometric probability, the "Connect the Dots" problem asks: if $n$ points are scattered randomly in a square, what is the maximum number of points, $N_n$, that a "well-behaved" (regular) curve can pass through? This problem serves as a continuous, geometric analogue to the classic "Longest Increasing Subsequence" problem. The original work by Arias-Castro et al. (2005) sought to establish these limits for various curve classes, such as Lipschitz graphs. However, a mathematical slip in the asymptotic constant and a mislabeling of parameters in numerical simulations necessitated this formal correction.

Theoretical Refinement

The primary theoretical contribution of this correction is the re-evaluation of the asymptotic behavior of the median number of points. The authors determined that the previously stated limit was off by a factor of $\sqrt{2}$.

  • Original Statement: $Median(N_n) \sim 2\sqrt{n}$
  • Corrected Statement: $Median(N_n) \sim \sqrt{2n}$

This shift is significant for researchers using these results as theoretical benchmarks, as the specific constant determines the predicted density of optimal paths in geometric structures.

Experimental Verification

To validate the revised theoretical limit, the authors conducted new simulations using synthetically generated random point sets. They calculated the maximum number of points a Lipschitz graph with a constant of 1 ($LipGr_1$) could visit for sample sizes $n$ ranging from 512 to 4096.

Histograms of $N_n/\sqrt{n}$ for various sample sizes $n$, showing convergence to $\sqrt{2} \approx 1.414$.

By plotting the distribution of the normalized value $N_n/\sqrt{n}$, the authors provided visual and statistical evidence of the law of large numbers at work. As shown in the histograms above, as $n$ increases, the distribution becomes tighter and centers more precisely around the corrected value of $\sqrt{2} \approx 1.414$. Specifically, at $n=4096$, the peak is clearly situated between 1.4 and 1.45, offering strong empirical support for the $\sqrt{2n}$ limit.

Discussion and Transparency

A key insight from this correction is the importance of experimental transparency. The authors noted that a figure in the original 2005 paper claimed to represent results for a Lipschitz constant $L=1$ when it actually utilized $L=2$. This "experimental drift" highlights the necessity of re-verifying computational results against theoretical expectations.

While the current simulations up to $n=4096$ clearly demonstrate the trend, finding exact constants for more complex curve classes remains a challenge. Future work may require even larger simulations or more sophisticated combinatorial optimization algorithms to account for boundary effects and achieve higher-order precision.

Conclusion

By correcting the fundamental theorem regarding the median number of points to $Median(N_n) \sim \sqrt{2n}$, this document ensures that the geometric probability community has an accurate baseline for future research. The alignment between the refined theory and the new experimental data confirms the validity of the $\sqrt{2}$ constant for Lipschitz graphs.

Summary updated

Abstract

Given a class Γ of curves in [0, 1] 2 , we ask: in a cloud of n uniform random points, how many points can lie on some curve γ ∈ Γ? Classes studied here include curves of length less than or equal to L , Lipschitz graphs, monotone graphs, twice-differentiable curves, and graphs of smooth functions with m -bounded derivatives. We find, for example, that there are twice-differentiable curves containing as many as O P ( n 1/3 ) uniform random points, but not essentially more than this. More generally, we consider point clouds in higher-dimensional cubes [0, 1] d and regular hypersurfaces of specified codimension, finding, for example, that twice-differentiable k -dimensional hypersurfaces in R d may contain as many as O P ( n k /(2 d - k ) ) uniform random points. We also consider other notions of ‘incidence’, such as curves passing through given location/direction pairs, and find, for example, that twice-differentiable curves in R 2 may pass through at most O P ( n 1/4 ) uniform random location/direction pairs. Idealized applications in image processing and perceptual psychophysics are described and several open mathematical questions are identified for the attention of the probability community.
BibTeX
@inproceedings{ariascastro2005connect,
  author = {Ery Arias-Castro and David L. Donoho and Xiaoming Huo and Craig A. Tovey},
  title = {{Connect the dots: how many random points can a regular curve pass through?}},
  booktitle = {Advances},
  year = {2005},
  doi = {10.1017/s0001867800000379},
}
Figure