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.
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