Roughly speaking, a planar order type is a point set where we forget about

the coordinates of the points, but keep for each pair of points the

information which of the other points lie left and right of the line

connecting these two points. For example, assuming no three points lie on a

common line, there are exactly two 4-point order types: four points

which are vertices of a convex quadrilateral, or three points with the

fourth point inside the triangle formed by these three points.

We consider such order types of points in general position in the plane

and show that the expected number of extreme points in such an n-point

order type, chosen uniformly at random from all such order types, is

4+o(1). This implies that order types read off uniform random samples of a

convex planar domain, smooth or polygonal, are concentrated, i.e. we

typically encounter only a vanishing fraction of all order types via such a

sampling.

As a crucial step we analyze the orientation preserving symmetries of

order types of finite point sets in the projective plane, along the lines

of Felix Klein's characterization of the finite subgroups of the isometries

of the 2-dimensional sphere.

Joint work with Xavier Goaoc.

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria www.ist.ac.at © IST 2020