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

Given a class Gamma of curves in [0, 1](2), we ask: in a cloud of n uniform random points, how many points can lie on some curve gamma E I? 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/(2d-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.