Special GeomTop seminar: &quot;Sylvester's Four-Point Problem on Order Types&quot;

Date: Thursday, March 5, 2020 13:00 - 14:15
Speaker: Emo Welzl (ETH Zurich)
Location: Mondi Seminar Room 3, Central Building
Series: Mathematics and CS Seminar
Host: Uli Wagner
Contact: WAGNER Hubert

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.