KAIST Discrete Math Seminar

Many problems in discrete and computational geometry can be reduced to combinatorial questions concerning systems of segments or triangles in the plane. In spite of what (little) we can say about these planar questions, much less is known in higher dimensions. In this talk we will survey some of these questions and classical results, and present the following theorem: Let d>2 and n>d+1 and P a set of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any point p in P, the simplex spanned by Q and p does not contain the origin in its interior. This answers a question by R.Strausz, and along the way we strengthen the Colored Helly and Caratheodory theorems, due to L. Lovász and I. Bárány, respectively.

Joint work with János Pach and Helge Tverberg.