Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey

By Martin Tancer. 2011

60 citations recorded by the source corpus.

The task of this survey is to present various results on intersection patterns of convex sets. One of the main tools for studying intersection patterns is a point of view via simplicial complexes. We recall the definitions of so-called d-representable, d-collapsible, and d-Leray simplicial complexes, which are very useful for this study. We study the differences among these notions and also focus on computational complexity for recognizing them. A list of Helly-type theorems is presented in the survey. We also discuss the important role played by the above-mentioned notions for the theorems. We also consider intersection patterns of good covers, which generalize collections of convex sets (the sets may be “curvy”; however, their intersections cannot be too complicated). We mainly focus on new results.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f5df0941c286095c325a85dd74d315deee6b5987