Convex Hulls of Random Order Types
Xavier Goaoc, Emo Welzl · arXiv (Cornell University) · 2020
This dataset contains the reproducible research package for the preprint "Exact Value of M(8) and Sharp Bounds for Great-Circle Cell Expectations", addressing Oberwolfach Report 3/2024 "Open Problems in Discrete Geometry", Problem 8 (posed by Xavier Goaoc). Problem. Let S be a simple arrangement of n great circles on the sphere S^2 and choose a 2-dimensional cell c uniformly at random. Let S' be the circles that do not touch c, and let c' be the cell of the subarrangement S' that contains c. Define M(n) as the maximum, over all simple arrangements, of the expected number of edges of c'. Main results: - Theorem 1: exact value M(8) = 113/29, obtained by exhaustive enumeration over all 3,315 simple 8-point order types in the Aichholzer database; the extremal order-type index is 1026. - Theorem 2: for the regular near-pencil family, the closed-form expectation E[x] = (8 n^2 - 36 n) / (n^2 - n + 2) = 8 - O(1/n), giving M(n) >= 8 - O(1/n) for all n >= 6. - Theorem 3: general upper bound M(n) = 3. - Conjecture: the matching upper bound M(n) <= 8 + o(1) remains open; M(n) = 8 - o(1) is therefore a conjecture supported by numerical experiments. The archive includes Python scripts (MIT License), JSON data certificates and the Aichholzer order-type database (CC0 1.0 Universal), proof notes, review reports, and the preprint in PDF and Markdown form (CC-BY 4.0). Limitations: exact values are known only for n <= 8; the asymptotic upper bound is not proved.