Random Convex Hulls and Extreme Value Statistics

Abstract

In this paper we study the statistical properties of convex hulls of $N$ random points in a plane chosen according to a given distribution. The points may be chosen independently or they may be correlated. After a non-exhaustive survey of the somewhat sporadic literature and diverse methods used in the random convex hull problem, we present a unifying approach, based on the notion of support function of a closed curve and the associated Cauchy's formulae, that allows us to compute exactly the mean perimeter and the mean area enclosed by the convex polygon both in case of independent as well as correlated points. Our method demonstrates a beautiful link between the random convex hull problem and the subject of extreme value statistics. As an example of correlated points, we study here in detail the case when the points represent the vertices of $n$ independent random walks. In the continuum time limit this reduces to $n$ independent planar Brownian trajectories for which we compute exactly, for all $n$, the mean perimeter and the mean area of their global convex hull. Our results have relevant applications in ecology in estimating the home range of a herd of animals. Some of these results were announced recently in a short communication [Phys. Rev. Lett. {\bf 103}, 140602 (2009)].

61 pages (pedagogical review); invited contribution to the special issue of J. Stat. Phys. celebrating the 50 years of Yeshiba/Rutgers meetings

References in corpus (29)

• Large Deviations of Extreme Eigenvalues of Random Matrices
• Extreme Value Statistics of Eigenvalues of Gaussian Random Matrices
• Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
• Large Deviations of the Maximum Eigenvalue for Wishart and Gaussian Random Matrices
• Universal Record Statistics of Random Walks and Lévy Flights
• Large Deviations of the Maximum Eigenvalue in Wishart Random Matrices
• Exact distribution of the maximal height of p vicious walkers
• On the time to reach maximum for a variety of constrained Brownian motions
• Extreme value problems in Random Matrix Theory and other disordered systems
• Density of near-extreme events
• Extreme value statistics from the Real Space Renormalization Group: Brownian Motion, Bessel Processes and Continuous Time Random Walks
• Records in a changing world
• Condensation and Extreme Value Statistics
• Unified Solution of the Expected Maximum of a Random Walk and the Discrete Flux to a Spherical Trap
• Extreme statistics for time series: Distribution of the maximum relative to the initial value
• Exact Minimum Eigenvalue Distribution of an Entangled Random Pure State
• A record-driven growth process
• Universal Extremal Statistics in a Freely Expanding Jepsen Gas
• Distribution of the time at which the deviation of a Brownian motion is maximum before its first-passage time
• Statistical Properties of the Final State in One-dimensional Ballistic Aggregation
• Exact solution of a model of time-dependent evolutionary dynamics in a rugged fitness landscape
• The longest excursion of fractional Brownian motion : numerical evidence of non-Markovian effects
• Probability distribution of the maximum of a smooth temporal signal
• Statistical properties of single-file diffusion front
• Crowding at the Front of the Marathon Packs
• Maximum relative height of one-dimensional interfaces : from Rayleigh to Airy distribution
• Contest based on a directed polymer in a random medium
• The mean perimeter of some random plane convex sets generated by a Brownian motion
• Multiparticle random walks

Cited by in corpus (59)

• Extreme value statistics of correlated random variables: a pedagogical review
• Universal First-passage Properties of Discrete-time Random Walks and Levy Flights on a Line: Statistics of the Global Maximum and Records
• Spatial extent of an outbreak in animal epidemics
• Generalised `Arcsine' laws for run-and-tumble particle in one dimension
• The convex hull of the run-and-tumble particle in a plane
• Extremal statistics of curved growing interfaces in 1+1 dimensions
• Distribution of the time at which N vicious walkers reach their maximal height
• Mean perimeter and area of the convex hull of a planar Brownian motion in the presence of resetting
• Distribution of the time of the maximum for stationary processes
• Time between the maximum and the minimum of a stochastic process
• Unravelling intermittent features in single particle trajectories by a local convex hull method
• Distribution of the Time Between Maximum and Minimum of Random Walks
• Convex Hulls of Random Walks: Large-Deviation Properties
• Volumetric Properties of the Convex Hull of an n-dimensional Brownian Motion
• The convex hull for a random acceleration process in two dimensions
• Time to reach the maximum for a stationary stochastic process
• Maximum of N Independent Brownian Walkers till the First Exit From the Half Space
• Mean area of the convex hull of a run and tumble particle in two dimensions
• Discrete Sampling of Extreme Events Modifies Their Statistics
• Learning in High Dimension Always Amounts to Extrapolation
• Survival probability of a Brownian motion in a planar wedge of arbitrary angle
• Convex hulls of random walks and their scaling limits
• Generating discrete-time constrained random walks and Lévy flights
• Convex hull of a Brownian motion in confinement
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• Roots of random polynomials whose coefficients have logarithmic tails
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Smoluchowski flux and Lamb-Lion Problems for Random Walks and Lévy Flights with a Constant Drift
• Generating stochastic trajectories with global dynamical constraints
• Exact distributions of cover times for $N$ independent random walkers in one dimension
• The convex hull of a planar random walk: perimeter, diameter, and shape
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Generating constrained run-and-tumble trajectories
• Last-passage time for linear diffusions and application to the emptying time of a box
• Slow Kinetics of Brownian Maxima
• Mean perimeter of the convex hull of a random walk in a semi-infinite medium
• Extreme-value statistics from Lagrangian convex hull analysis for homogeneous turbulent Boussinesq convection and MHD convection
• Estimating the probability that a given vector is in the convex hull of a random sample
• Generalized arcsine laws for a sluggish random walker with subdiffusive growth
• Large Deviations of Convex Hulls of the "True" Self-Avoiding Random Walk
• Large deviations in statistics of the convex hull of passive and active particles: A theoretical study
• Convex hull of n planar Brownian paths: an exact formula for the average number of edges
• Algebraic and arithmetic area for $m$ planar Brownian paths
• Random Gaussian Tetrahedra
• Iterated-logarithm laws for convex hulls of random walks with drift
• Exact joint distributions of three global characteristic times for Brownian motion
• First-passage and extreme value statistics for overdamped Brownian motion in a linear potential
• Large deviations of a random walk model with emerging territories
• Capturing, Ordering and Gaussianity in 2D
• A Decomposition Algorithm for Nested Resource Allocation Problems
• Convex hulls of random walks: Expected number of faces and face probabilities
• More on the convergence of Gaussian convex hulls
• Errata and Addenda to Mathematical Constants
• Convex hulls of planar random walks
• On sequences of convex records in the plane
• On the convex hull of symmetric stable processes
• On convex hull of Gaussian samples
• Survival probability of random walks leaping over traps
• On the asymptotic of convex hulls of Gaussian fields