Thursday, February 12, 2004
Ery Arias-Castro
Department of Statistics
Stanford University
Title: Connect-The-Dots: How many random points can a regular curve pass through?
Abstract: Suppose n points are scattered uniformly at random in the unit square. Question: How many of these points can possibly lie on some curve of length bounded by L? Answer, proved here: order the square root of n.
We consider a general class of such questions; in each case, we are given a class G of curves in the square, and we ask: in a cloud of n uniform random points, how many can lie on some curve g in G? Classes of interest include (in addition to the rectifiable curves mentioned above): Lipschitz curves, increasing curves, twice-differentiable curves, smooth curves with m-bounded derivatives. In each case we get order-of-magnitude estimates; for example, there are twice-differentiable curves containing as many as order n to the third uniform random points, but not essentially more than this.
We also consider generalizations to higher dimensions and to hypersurfaces of various co-dimensions. Thus, twice-differentiable k-dimensional hypersurfaces in dimension d may contain as many as n to the power k/(2d-k) uniform random points. We also consider other notions of `passing through' such as passing through given space/direction pairs. Thus, twice-differentiable curves in 2D may pass through at most order n to the fourth uniform random points.
We give both concrete approaches to our results, based on geometric multiscale analysis, and abstract approaches, based on epsilon-Entropy. Stylized applications in image processing and perceptual psychophysics are described.
Seminar to be held in Room 107, 24 Hillhouse at 12:00 Noon