On convex holes in d-dimensional point sets

Seminar
Speaker
Ron Holzman (Technion)
Date
20/03/2022 - 15:30 - 14:00Add to Calendar 2022-03-20 14:00:00 2022-03-20 15:30:00 On convex holes in d-dimensional point sets Given a finite set $P \subseteq \mathbb{R}^d$, points $a_1, a_2, \dots, a_{\ell} \in P$ form an $\ell$-hole in $P$ if they are the vertices of a convex polytope which contains no points of $P$ in its interior.  We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $2^{7d}$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. Our construction uses a certain type of designs, originating from numerical analysis, known as ordered orthogonal arrays. The bound may be further improved, to roughly $4^d$, via an approximate version of such designs.  Joint work with Boris Bukh and Ting-Wei Chao. Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Zoom
Abstract

Given a finite set $P \subseteq \mathbb{R}^d$, points $a_1, a_2, \dots, a_{\ell} \in P$ form an $\ell$-hole in $P$ if they are the vertices of a convex polytope which contains no points of $P$ in its interior. 

We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $2^{7d}$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. Our construction uses a certain type of designs, originating from numerical analysis, known as ordered orthogonal arrays. The bound may be further improved, to roughly $4^d$, via an approximate version of such designs. 

Joint work with Boris Bukh and Ting-Wei Chao.

Last Updated Date : 15/03/2022