Concentration in order types of random point sets

Abstract: The order type of a planar point set is a combinatorial structure that encodes many of its geometric properties, for instance the face lattice of its convex hull or the triangulations it supports. In a sense, it is a generalization of the permutation associated to a sequence of real numbers.

This talk will start with a quick introduction to order types. Then, I'll discuss a concentration phenomenon that arises when taking order types of various natural models of random point sets, and that makes order types hard to sample efficiently. This will give us an occasion to revisit Klein's celebrated proof of the classification of finite subgroups of SO(3).

This is joint work with Emo Welzl (https://arxiv.org/abs/2003.08456).

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

( paper )

---

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456

---