Department of Computer Science | Institute of Theoretical Computer Science | CADMO
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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 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