Maximal Minimal Spacing for Random Points
Open Access
- 27 August 2026
- journal article
- research article
- Published by Springer Nature in Journal of Statistical Physics
- Vol. 193 (9) , 118
Abstract
From $$N+1$$ random points on a line we wish to select $$M+1$$ points so as to maximize the minimal spacing between them. We consider an initial configuration with independent and identically distributed spacings. Equivalently, the points are arrival times of a generic renewal process. For general spacing distributions, and for all $$M\le N$$ , we derive exact distributional identities for the maximal minimal spacing and obtain its asymptotic behavior. The problem admits a reformulation in terms of a threshold-resetting random walk. The walk advances by successive random increments and is reset to the origin upon exceeding a fixed threshold. The probability that the optimal spacing exceeds a given value coincides with the probability that the walk completes at least M reset cycles within N steps. This yields an exact representation in terms of first-passage functionals of the walk. The same mapping suggests a numerical scheme for the max-min spacing problem in the regime of large N and M , whose accuracy is tested against the exact results obtained here.
Keywords
All Related Versions
Funding Information
- UK Research and Innovation (MR/X023028/1)
This publication has 29 references indexed in Scilit:
- A review on discrete diversity and dispersion maximization from an OR perspectiveEuropean Journal of Operational Research, 2022
- Max–min dispersion on a lineJournal of Combinatorial Optimization, 2020
- Exact Algorithms for the Max-Min Dispersion Problem2018
- A new compact formulation for the discrete p-dispersion problemEuropean Journal of Operational Research, 2017
- Limit results for ordered uniform spacingsStatistical Papers, 2008
- Facility dispersion problems: Heuristics and special cases2005
- Order Statistics2003
- The discrete p-dispersion problemEuropean Journal of Operational Research, 1990
- Analytical models for locating undesirable facilitiesEuropean Journal of Operational Research, 1989
- Elementary proofs of some basic facts concerning order statisticsActa Mathematica Hungarica, 1954