ACO Seminar
— 4:30pm
Location:
8220
-
Wean Hall
Speaker:
Zichao Dong
,
Doctoral Student,
Convex polytopes in non-elongated point sets in R^d
Abstract:
For any finite point set P⊂Rd, we denote by diam(P) the ratio of the largest to the smallest distances between pairs of points in P. Let cd,α(n) be the largest integer c such that any n-point set P⊂Rd in general position, satisfying diam(P)<αn−−√d (informally speaking, `non-elongated'), contains a convex c-polytope. Valtr proved that c2,α(n)≈n−−√3, which is asymptotically tight in the plane. We generalize the results by establishing cd,α(n)≈nd−1d+1. Along the way we generalize the definitions and analysis of convex cups and caps to higher dimensions, which may be of independent interest. This is a joint work with Boris Bukh.
Event Website:
https://aco.math.cmu.edu/abs-21-22/apr14.html
Contact
Andrew Newman