Longest convex chains with i.i.d. points
Abstract
Sample n i.i.d. points from a triangle, according to some continuous density function. Given two vertices A,B of the triangle, what is the maximum number of samples that form a convex chain with initial point A and terminal point B? We show that to leading order, the answer is cn1/3, generalizing a result of Ambrus and Bárány that considered uniformly distributed points. Furthermore, we express the constant c using a variational formula whose maximizer (if unique) gives the limiting curve formed by the longest convex chain. By comparison, for n i.i.d. samples from the unit square, the length of the longest monotone chain is asymptotically c'n1/2. Despite the difference in scale, our formula is nicely connected to one established for c' by Deuschel and Zeitouni.
Related
- Random tilts to find stationary points in stochastic convex optimization
- Maximal volume of convex bodies avoiding random points and lacunary dilates
- Unconstrained support points can leave a convex support
- A Brunn-Minkowski Theory for the Distribution of Random Pairs of Points in Convex Bodies
- Convex Curve Recovery in Phase Space Extreme Points and Exact Graph Discretization
BibTeX
@misc{bates2026longest,
title = {{Longest convex chains with i.i.d. points}},
author = {Erik Bates and Arnab Sen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09105},
eprint = {2608.09105},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09105},
}
RIS
TY - UNPB
TI - Longest convex chains with i.i.d. points
AU - Erik Bates
AU - Arnab Sen
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2608.09105
UR - https://arxiv.org/abs/2608.09105
AB - Sample n i.i.d. points from a triangle, according to some continuous density function. Given two vertices A,B of the triangle, what is the maximum number of samples that form a convex chain with initial point A and terminal point B? We show that to leading order, the answer is cn^1/3, generalizing a result of Ambrus and Bárány that considered uniformly distributed points. Furthermore, we express the constant c using a variational formula whose maximizer (if unique) gives the limiting curve formed by the longest convex chain. By comparison, for n i.i.d. samples from the unit square, the length of the longest monotone chain is asymptotically c'n^1/2. Despite the difference in scale, our formula is nicely connected to one established for c' by Deuschel and Zeitouni.
ER -