Connect the dots: how many random points can a regular curve pass through?
Ery Arias-Castro, David L. Donoho, Xiaoming Sharon Huo, Craig A. Tovey · Advances in Applied Probability · 2005
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.