Personal tools
You are here: Home CG seminar 2021 Convex Hulls of Random Order Types
« October 2021 »
Log in

Forgot your password?

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


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.


Document Actions