Correction. Connect The Dots: How Many Random Points Can A Regular Curve Pass Through?

Ery Arias-Castro, David L. Donoho, Xiaoming Huo, Craig A. Tovey

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

Correction for Adv. in Appl. Probab. 37, no. 3 (2005), 571-603
BibTeX
@inproceedings{ariascastro2006correction,
  author = {Ery Arias-Castro and David L. Donoho and Xiaoming Huo and Craig A. Tovey},
  title = {{Correction. Connect The Dots: How Many Random Points Can A Regular Curve Pass Through?}},
  booktitle = {Advances},
  year = {2006},
  doi = {10.1239/aap/1151337086},
}
Figure