In:
Advances in Applied Probability, Cambridge University Press (CUP), Vol. 37, No. 3 ( 2005-09), p. 571-603
Abstract:
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.
Type of Medium:
Online Resource
ISSN:
0001-8678
,
1475-6064
DOI:
10.1239/aap/1127483737
Language:
English
Publisher:
Cambridge University Press (CUP)
Publication Date:
2005
detail.hit.zdb_id:
1474602-5
Permalink