Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, March 19, 2020, 12:15 pm

Duration: 30 minutes

Location: Zoom: https://ethz.zoom.us/j/630077105

Speaker: Emo Welzl

Sylvester’s Four-Point Problem on Order Types

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login