Here is a list of publication by chronological order and another one by publication type (on HAL).


1. Combinatorial geometry and topology

A survey of relations between five elementary results in discrete topology and discrete geometry, as well as applications in game theory and fair division, graph theory, optimization and geometric data analysis.

  • The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
    J. A. De Loera, X. Goaoc, F. Meunier and N. Mustafa

Some complexity results...

Some results around non-embeddability...

A study of intersection pattern via generalized nerve complexes, with application to geometric transversal theory.

  • Multinerves and Helly numbers of acyclic families
    E. Colin De Verdière, G. Ginot, and X. Goaoc
    Advances in Mathematics 253: 163--193
    Proceedings of SoCG 2012 (under a slightly different name)

2. Random geometric structures

These papers examine some geometric structures (convex hull and Delaunay triangulation) induced by random point sets.

  • 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
  • Expands two earlier conference papers:

    • On the smoothed complexity of convex hulls
      O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse.
    • Complexity analysis of random geometric structures made simpler
      O. Devillers, M. Glisse, and X. Goaoc.
      see also the Inria research reports 8168 and 7134
  • 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
    Proceedings of SODA 2008 (pp. 1249-1257)
    pdf file (No journal version is planned)

3. Extremal combinatorics for geometry

These papers adapt to geometric structures some techniques from extremal combinatorics.


  • Shatter functions with polynomial growth rates
    B. Bukh and X. Goaoc
  • Limits of order types
    X. Goaoc, A. Hubard, R. de Joannis de Verclos, J.-S. Sereni, and Jan Volec
  • 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
    arXiv:0912.2979 (slightly outdated)

4. Line geometry and geometric transversals

Some papers exploring questions on line geometry raised by computer vision.

  • Consistent sets of lines with no colorful incidence
    B. Bukh, X. Goaoc, A. Hubard, and M. Tragger
    Accepted to SoCG 2018
  • Admissible Linear Map Models of Linear Cameras
    G. Batog, X. Goaoc, and J. Ponce
    Proceedings of CVPR 2010
    pdf file (no journal version yet)
    See also Guillaume's Phd thesis (in french)

In how many different ways, that is geometric permutations, can one stab disjoint unit balls?

  • Geometric permutations of non-overlapping balls revisited
    J.-S. Ha, O. Cheong and X. Goaoc
    Computational Geometry: Theory and Applications 53: 36-50, 2016
  • Geometric permutations of disjoint unit spheres
    O. Cheong, X. Goaoc and H.-S. Na
    Computational Geometry: Theory and Applications 30(3): 253-270, 2005
    Proceedings of ESA 2003

A proof of a Helly-type theorem for sets of line transversals to disjoint unit balls conjectured by Danzer and related questions.

Helly-type theorems for isolated line transversals.

Overview of how the three topics above (geometric permutations, Danzer's conjecture and Helly-type theorems for isolated transversals) are related.

  • Transversal Helly numbers, pinning theorems and projection of simplicial complexes
    Habilitation thesis from Université Henri Poincaré - Nancy 1, December 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

5. 3D visibility

Approximate algorithms for visibility query from Helly-type theorems.

Some bounds on the complexity of data structures for 3D visibility.

  • 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
    Proceedings of SoCG 2004
  • 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

A characterization of degeneracies for visibiility among balls in 3D.

  • Common Tangents to Spheres in R3
    C. Borcea, X. Goaoc, S. Lazard, and S. Petitjean
    Discrete & Computational Geometry 35(2): 287-300, 2006
    See the (much expanded) related preprint arXiv:math/0402394

My PhD thesis, gathering (and expanding) the two topics above: complexity an degeneracies of 3D visibility structures.

  • Structures de visibilité globale : taille, calcul et dégénerescences
    PhD thesis from Université Nancy 2, May 2004

6. Other topics

A reduction of the computation of the shortest bounded curvature path through a sequence of points (in a given order; this is not TSP) to a family of convex optimization problems.

Some other various works

  • 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
  • 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
    Proceedings of GD 2007
  • A polynomial-time algorithm to design push plans for sensorless parts sorting
    M. de Berg, X. Goaoc and A. F. Van der Stappen
    Proceedings of Robotics Science and Systems (RSS), 2005
    pdf file (no journal version is planned)