# Convex Hulls of Random Order Types

### Wednesday, May 5th, 2020, 16:10

~~Checkpoint 480~~

### Zoom: Request the link from Dan Halperin or Golan Levy

### Convex Hulls of Random Order Types

### Xavier Goaoc, Ă‰cole des Mines de Nancy and LORIA

### Abstract:

I will present a joint work with Emo Welzl, in which we study order

types of points in general position in the plane (realizable simple

planar order types, realizable uniform acyclic oriented matroids of

rank 3). We establish the following two main results:

- The number of extreme points in an n-point 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

exactly 4-8/(n^2-n+2) and variance at most 3.

- 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.

The results on unlabeled order types depend on characterizing the

possible groups of orientation preserving bijections of an antipodal,

finite subset of the 2-dimensional sphere. We prove that any such

group must be cyclic, dihedral or one of A_4, S_4 or A_5 (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.