Xavier Goaoc

• algorithmes et complexité. Cours de tronc commun de 1ère année (9x3h). Introduit à l'informatique théorique (modèles de calcul, conception et analyse d'algorithmes, complexité des problèmes, NP-difficulté).


• architecture des ordinateurs. Cours de 2ème année du département informatique (7x3h). Aborde les hiérarchies mémoire, l'assembleur x86 et l'analyse de code compilé par gcc, le pipeline et la prédiction de branchement, la vectorisation.


• introductions aux blockchaines. Cours électif de 2ème année (7x3h). Aborde le hachage et les signatures cryptographique, les principes de calcul distribué, les principes de la blockchaine de bitcoin, le théorème de Fischer, Lynch, Paterson et le théorème Lamport-Shostak-Pease, les algorithmes Paxos et BBA*.

• algorithmes et complexité, cours de tronc commun scientifique, 1ère année d'Ingénieur Civil des Mines
• architecture des ordinateurs, cours de département informatique, 2ème année d'Ingénieur Civil des Mines
• introduction aux blockchains, cours électif transverse, 2ème année d'Ingénieur Civil des Mines
• modélisation géométrique et planification de trajectoire, cours de M2 informatique (parcours AVR), partagé avec Francis Colas et Olivier Devillers
• algorithmes de consensus et blockchains, cours de 5ème année de spécialité programmation et réseau à Polytech Nancy

• 2021-2022 : architecture avancée, introduction aux blockchaines, algorithmes et complexité, consensus et blockchains
• 2020-2021 : algorithmique avancée, architecture avancée, introduction aux blockchaines, algorithmes et complexité, algorithmique distribuée, apprentissage automatique (TD), recherche opérationnelle (TD)
• 2019-2020 : algorithmique avancée, architecture avancée, introduction aux blockchaines, recherche opérationelle (TD), algorithmique-programmation (TD)
• 2018-2019 : algorithmique avancée, architecture avancée
• 2017-2018 : architecture avancée, mathématiques discrètes (isopérimétries), fondements de l'optimisation
• 2016-2017 : architecture avancée, mathématiques discrètes (isopérimétries)
• 2015-2016 : architecture des ordinateurs, mathématiques discrètes (géométrie)
• 2014-2015 : optimisation combinatoire, architecture des ordinateurs
• 2013-2014 : architecture des ordinateurs, probabilités pour informaticien, programmation en C, optimisation combinatoire, mathématiques discrètes pour informaticiens

My research is in algorithms and discrete mathematics, more precisely in the area of discrete and computational geometry.

Most of my work is on discrete structures that arise from geometric data, for instance convex hull of point sets or intersection patterns of families of sets. I try to understand how the geometry of the data influences these structures, with an emphasis on properties related to computation (e.g. Helly-type theorems which play a role in optimization).

I often use topology (e.g. the nerve theorem or non-embedability results), probabilities (e.g. negative association or discrete-continuous equivalences) and combinatorics (e.g. Ramsey theory or forbidden structures)... and of course geometry in many forms. I am particularly fond of the line geometry pioneered by Plücker, Klein, Grassmann...

Here is a complete list of my publications (by type, reverse-chronological).

Below are my main publications organized by topics. You'll also find some of my papers on arXiv and on HAL.

INRIA associate team FIP

• Convex hulls of random order types, X. Goaoc and E. Welzl. Journal of the ACM, 70(1): 1--47, 2023. (A preliminary version received the best paper award at SoCG'20.)
• A Stepping-Up Lemma for Topological Set Systems, X. Goaoc, A. Holmsen and Z. Patáková. Proceedings of SoCG 2021.
• Random polytopes and the wet part for arbitrary probability distributions, I. Bárány, M. Fradelizi, X. Goaoc, A. Hubard and G. Rote. Annales Henri Lebesgue 3:701-715, 2020.
• Shatter functions with polynomial growth rates, B. Bukh and X. Goaoc. SIAM J. Discrete Math. 33(2): 784-794, 2019.
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, J. A. De Loera, X. Goaoc, F. Meunier and N. Mustafa. Bulletin of the American Mathematical Society 56:415-511, 2019.
• Shellability is NP-complete, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Journal of the ACM 66(3): article 21, 2019. (A preliminary version received the best paper award at SoCG 2018, pp 41:1--15.)
• The number of holes in the union of translates of a convex set in three dimensions, B. Aronov, O. Cheong, M. G. Dobbins, and X. Goaoc. Discrete & Computational Geometry 57(1): 104--124, 2017. (A preliminary version received the best paper award at SoCG 2016.)
• Simplifying inclusion-exclusion formulas, X. Goaoc, J. Matousek, P. Paták, Z. Safernová, and M. Tancer. Combinatorics, Probability and Computing 24(2): 438--456, 2015.
• Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.)
• Bounded-Curvature Shortest Path Through a Sequence of Points Using Convex Optimization, X. Goaoc, H.-S. Kim, and S. Lazard. SIAM Journal on Computing 42(2): 662--684, 2013.
• Admissible Linear Map Models of Linear Cameras, G. Batog, X. Goaoc, and J. Ponce. CVPR 2010.

(A handful of papers appear in more than one topic.)

... on homological minors Uli Wagner proposed an homological version of graph minors for simplicial complexes. Here are some applications of this notion. A Stepping-Up Lemma for Topological Set Systems, X. Goaoc, A. Holmsen and Z. Patáková. Proceedings of SoCG 2021. Bounding Helly numbers via Betti numbers, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. A Journey Through Discrete Mathematics, pp 407--447, 2017. (A preliminary version appeared in the proceedings of SoCG 2015, pp 507--521.) On generalized Heawood inequalities for manifolds: a Van Kampen-Flores-type nonembeddability result, X. Goaoc, I. Mabillard, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Israel Journal of Maths 222: 841--866, 2017. (A preliminary version appeared in the proceedings of SoCG 2015, pp 507--521.)

... on the combinatorics of simplicial complexes Abstract simplicial complex are elementary combinatorial structures, really a subclass of hypergraphs, that, like planar graphs, can be interpreted as triangulations of topological spaces. Their study combines combinatorics and topology beautifully. Convexité combinatoire (in french), X. Goaoc. Informatique mathématique, une photographie en 2020, pp 151--201, 2020. Shellability is NP-complete, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Journal of the ACM 66(3): article 21, 2019. (A preliminary version received the best paper award at SoCG 2018, pp 41:1--15.) Shatter functions with polynomial growth rates, B. Bukh and X. Goaoc. SIAM J. Discrete Math. 33(2): 784-794, 2019. Simplifying inclusion-exclusion formulas, X. Goaoc, J. Matousek, P. Paták, Z. Safernová, and M. Tancer. Combinatorics, Probability and Computing 24(2): 438--456, 2015. Set Systems and Families of Permutations with Small Traces, O. Cheong, X. Goaoc, and C. Nicaud. European Journal of Combinatorics 34(2): 229--239, 2013.

... on random geometric structures These papers investigate the combinatorial complexity of discrete structures (such as polytopes) defined by random point sets. Random polytopes and the wet part for arbitrary probability distributions, I. Bárány, M. Fradelizi, X. Goaoc, A. Hubard and G. Rote. Annales Henri Lebesgue 3:701-715, 2020. Smoothed complexity of convex hulls by witnesses and collectors, O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse. Journal of Computational Geometry 7(2): 101--144, 2016. (Preliminary versions appeared in the proceedings of SoCG 2013 and SoCG 2015.) The monotonicity of f-vectors of random polytopes, O. Devillers, M. Glisse, X. Goaoc, G. Moroz, and M. Reitzner. Electronic Communications in Probability 18: art. 23, pp 1--8, 2013. Empty-ellipse graphs, O. Devillers, J. Erickson, and X. Goaoc. SODA 2008, pp. 1249--1257. The expected number of 3D visibility events is linear, O. Devillers, V. Dujmovic, H. Everett, X. Goaoc, S. Lazard, H.-S. Na, and S. Petitjean. SIAM Journal on Computing 32(6): 1586-1620, 2003.

... on order types of point sets Order types are combinatorial structures that arise from finite (planar) point sequences, in the same way as permutations arise from finite sequences of real numbers. I am interested in random generation methods that produce "interesting" order types. This proves surprisingly difficult... Convex hulls of random order types, X. Goaoc and E. Welzl. Journal of the ACM, 70(1): 1--47, 2023. (A preliminary version received the best paper award at SoCG'20.) Limits of order types (expanded version), X. Goaoc, A. Hubard, R. de Joannis de Verclos, J.-S. Sereni, and J. Volec. 2018. (A preliminary version appeared in SoCG 2015, pp 300-314.) On Order Types of Random Point Sets, O. Devillers, P. Duchon, M. Glisse and X. Goaoc. 2018

... on combinatorial convexity and its topological generalizations Combinatorial convexity studies the intersection patterns of families of convex sets, with a particular attention to the systems of convex hulls of finite subsets of a point set. It grew out of the theorems of Helly, Radon and Carathéodory and flourished in a rich and beautiful theory with surprising connections. I am interested in relaxing convexity into weaker topological assumptions. The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, J. A. De Loera, X. Goaoc, F. Meunier and N. Mustafa. Bulletin of the American Mathematical Society 56:415-511, 2019. Convexité combinatoire (in french), X. Goaoc. Informatique mathématique, une photographie en 2020, pp 151--201, 2020. A Stepping-Up Lemma for Topological Set Systems, X. Goaoc, A. Holmsen and Z. Patáková. Proceedings of SoCG 2021. Bounding Helly numbers via Betti numbers, X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. A Journey Through Discrete Mathematics, pp 407--447, 2017. (A preliminary version appeared in the proceedings of SoCG 2015, pp 507--521.) Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.)

... on geometric transversal theory Combinatorial convexity can be extended by considering not only points common to families of convex sets, but lines piercing families of convex sets. See here for a sample. I am interested in geometric permutations and worked on some conjectures of Danzer. No weak epsilon nets for lines and convex sets in space, O. Cheong, X. Goaoc and A. Holmsen. 2022 The Topology of the set of line Transversals, O. Cheong, X. Goaoc and A. Holmsen. 2022 An experimental study of forbidden patterns in geometric permutations by combinatorial lifting, X. Goaoc, A. Holmsen and C. Nicaud. Journal of Computational Geometry 11(2):131--161, 2021.(A preliminary version appeared in the proceedings of SoCG 2019.) Helly numbers of acyclic families, E. Colin De Verdière, G. Ginot, and X. Goaoc. Advances in Mathematics 253: 163--193, 2014. (A preliminary version received the best paper award at SoCG 2012.) Transversal Helly numbers, pinning theorems and projection of simplicial complexes, Habilitation thesis, December 2011. Papers covered by the habilitation Geometric permutations of non-overlapping balls revisited, J.-S. Ha, O. Cheong and X. Goaoc. Computational Geometry: Theory and Applications 53: 36--50, 2016. Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls, O. Cheong, X. Goaoc, and A. Holmsen. Israël Journal of Mathematics 190(1): 213--228, 2012. Lines pinning lines, B. Aronov, O. Cheong, X. Goaoc, and G. Rote. Discrete & Computational Geometry 45(2) :230--260, 2011. Pinning a line by balls or ovaloids in R3, X. Goaoc, S. Konig, and S. Petitjean. Discrete & Computational Geometry 45(2): 303--320, 2011. Some Discrete Properties of the Space of Line Transversals to Disjoint Balls, X. Goaoc. Non-linear Computational Geometry, IMA Volume Series 151: 51--84, 2009. Line transversals to disjoint balls, C. Borcea, X. Goaoc, and S. Petitjean. Discrete & Computational Geometry 39(1-3): 158--173, 2008. (A preliminary version appeared in the proceedings of SoCG 2007.) Helly-Type Theorems for Line Transversals to Disjoint Unit Balls, O. Cheong, X. Goaoc, A. Holmsen, and S. Petitjean. Discrete & Computational Geometry 39(1-3): 194-212, 2008. (A preliminary version appeared in the proceedings of SoCG 2005.) Geometric permutations of disjoint unit spheres, O. Cheong, X. Goaoc and H.-S. Na. Computational Geometry: Theory and Applications 30(3): 253--270, 2005. (A preliminary version appeared in the proceedings of ESA 2003.)

... on line geometry for models of imaging systems Line geometry is also useful for the analysis of geometric models of imaging systems. Here are some examples. Consistent sets of lines with no colorful incidence, B. Bukh, X. Goaoc, A. Hubard, and M. Trager. SoCG 2018, pp 17:1--14. Admissible Linear Map Models of Linear Cameras, G. Batog, X. Goaoc, and J. Ponce. CVPR 2010. Common Tangents to Spheres in R3, C. Borcea, X. Goaoc, S. Lazard, and S. Petitjean. Discrete & Computational Geometry 35(2): 287--300, 2006.

... on the complexity of geometric data structures The number of holes in the union of translates of a convex set in three dimensions, B. Aronov, O. Cheong, M. G. Dobbins, and X. Goaoc. Discrete & Computational Geometry 57(1): 104--124, 2017. (A preliminary version received the best paper award at SoCG 2016.) Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra, H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. SIAM Journal on Computing 37(2): 522--551, 2007. (A preliminary version appeared in the proceedings of SoCG 2004.) Structures de visibilité globale : taille, calcul et dégénerescences, Phd thesis, May 2004.

... on geometric optimization Bounded-Curvature Shortest Path Through a Sequence of Points Using Convex Optimization, X. Goaoc, H.-S. Kim, and S. Lazard. SIAM Journal on Computing 42(2): 662--684, 2013. Inflating balls is NP-hard, G. Batog and X. Goaoc. International Journal of Computational Geometry and Applications 21(4): 403--415, 2011. Helly-type theorems for approximate covering, J. Demouth, O. Devillers, M. Glisse, and X. Goaoc. Discrete & Computational Geometry 42(3): 379--398, 2009. (A preliminary version appeared in the proceedings of SoCG 2008.) Untangling a Planar Graph, X. Goaoc, J. Kratochvil, Y. Okamoto, C.-S. Shin, A. Spillner, and A. Wolff. Discrete & Computational Geometry 42(4): 542--569, 2009. (A preliminary version appeared in the proceedings of Graph Drawing 2007.) A note on maximally repeated sub-patterns of a point set, V. Cortier, X. Goaoc, M. Lee, and H.-S. Na. Discrete Mathematics 306(16): 1965--1968, 2006. A polynomial-time algorithm to design push plans for sensorless parts sorting, M. de Berg, X. Goaoc and A. F. Van der Stappen. RSS 2005.