Goaoc, Xavier ;
Welzl, Emo
Convex Hulls of Random Order Types
Abstract
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3):
(a) The number of extreme points in an npoint order type, chosen uniformly at random from all such order types, is on average 4+o(1). For labeled order types, this number has average 48/(n^2  n +2) and variance at most 3.
(b) The (labeled) order types read off a set of n points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of extreme points 2d+o(1) and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods allow to show the following relative of the ErdősSzekeres theorem: for any fixed k, as n → ∞, a proportion 1  O(1/n) of the npoint simple order types contain a triangle enclosing a convex kchain over an edge.
For the unlabeled case in (a), we prove that for any antipodal, finite subset of the 2dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral or one of A₄, S₄ or A₅ (and each case is possible). These are the finite subgroups of SO(3) and our proof follows the lines of their characterization by Felix Klein.
BibTeX  Entry
@InProceedings{goaoc_et_al:LIPIcs:2020:12207,
author = {Xavier Goaoc and Emo Welzl},
title = {{Convex Hulls of Random Order Types}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {49:149:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12207},
URN = {urn:nbn:de:0030drops122074},
doi = {10.4230/LIPIcs.SoCG.2020.49},
annote = {Keywords: order type, oriented matroid, Sylvester’s FourPoint Problem, random convex hull, projective plane, excluded pattern, Hadwiger’s transversal theorem, hairy ball theorem}
}
08.06.2020
Keywords: 

order type, oriented matroid, Sylvester’s FourPoint Problem, random convex hull, projective plane, excluded pattern, Hadwiger’s transversal theorem, hairy ball theorem 
Seminar: 

36th International Symposium on Computational Geometry (SoCG 2020)

Issue date: 

2020 
Date of publication: 

08.06.2020 