Publications (32)
A canonical tree decomposition for order types, and some applications
Mathilde Bouvel, Valentin Féray, Xavier Goaoc +1
We introduce and study a notion of decomposition of planar point sets (or rather of their chirotopes) as trees decorated by smaller chirotopes. This decomposition is based on the c…
The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Jesus A. De Loera, Xavier Goaoc, Frédéric Meunier +1
We discuss five discrete results: the lemmas of Sperner and Tucker from combinatorial topology and the theorems of Carathéodory, Helly, and Tverberg from combinatorial geometry. W…
Convex Hulls of Random Order Types
Xavier Goaoc, Emo Welzl
We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented mat…
Random polytopes and the wet part for arbitrary probability distributions
Imre Bárány, Matthieu Fradelizi, Xavier Goaoc +2
We examine how the measure and the number of vertices of the convex hull of a random sample of points from an arbitrary probability measure in relates to the wet…
Consistent sets of lines with no colorful incidence
Boris Bukh, Xavier Goaoc, Alfredo Hubard +1
We consider incidences among colored sets of lines in and examine whether the existence of certain concurrences between lines of colors force the existence of at…
Shellability is NP-complete
Xavier Goaoc, Pavel Paták, Zuzana Patáková +2
We prove that for every , deciding if a pure, -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Dan…