Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 19, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: https://ethz.zoom.us/j/630077105
Speaker: Emo Welzl
Due to the situation with Covid-19, the talk will be done online, using Zoom. The link to the room is: https://ethz.zoom.us/j/630077105.
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.
Automatic MiSe System Software Version 1.4803M | admin login