1. Combinatorial geometry and topology

These papers revisit some classical topics in combinatorial geometry (Helly's theorems, planarity, union complexity...) by topological methods (nerve theorems and homological algebra).



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
    Inria research report 8787
  • 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.
      Proceedings of SoCG 2013
      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 geometric structures

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

Linear cameras. This paper presents a fairly general model of imaging systems based on linear line congruences. Explicit formulas for direct and inverse projections as well as stereoreconstruction methods for these models are presented.

Helly-type theorems for line transversals. In these papers we establish that the Helly number of sets of lines transversals to disjoint balls in Rd is between 2d-1 and 4d-1 (later improved to 4d-2 by topological methods, see above). This settled a conjecture of Danzer from 1957. The proof uses bounds on numbers of geometric permutations and a convexity property of sets of directions of line transversals further studied in separate papers.

  • Transversal Helly numbers, pinning theorems and projection of simplicial complexes
    Habilitation thesis from Université Henri Poincaré - Nancy 1, December 2011
    manuscript and slides (in english)
  • 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
    arXiv:0906.2924
  • Inflating balls is NP-hard
    G. Batog and X. Goaoc
    International Journal of Computational Geometry and Applications 21(4): 403--415, 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
  • 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
    Proceedings of SoCG 2005 (preliminary version)

Geometric permutations. In these papers, we establish bounds on the number of different orders in which a line can intersect a given family of disjoint unit balls in Rd. This is one key ingredient of the proof of Danzer's conjecture (see above).

  • Geometric permutations of non-overlapping balls revisited
    J.-S. Ha, O. Cheong and X. Goaoc
    Computational Geometry: Theory and Applications 53: 36--50, 2016
    arXiv:1407.0795
  • 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 (preliminary version)

Isolated line transversals. Another ingredient of the proof of Danzer's conjecture (see above) is a "local Helly-type theorem" for isolated line transversals to disjoint balls. The following papers study similar properties for polytopes and smooth convex sets.


5. 3D visibility

These papers present various results related to the complexity of 3D visibility data structures as well the question of detecting some of their degeneracies.

  • Helly-type theorems for approximate covering
    J. Demouth, O. Devillers, M. Glisse, and X. Goaoc
    Discrete & Computational Geometry 42(3): 379--398, 2009
    Proceedings of SoCG 2008
  • Structures de visibilité globale : taille, calcul et dégénerescences
    PhD thesis from Université Nancy 2, May 2004
    pdf file
  • 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 related preprint arXiv:math/0402394
  • 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 (preliminary version)
  • 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


6. Other topics

Bounded curvature path planning. In this paper we show that the problem of computing the shortest path through a sequence of points (in a given order; this is not TSP) reduces to a family of convex optimization problems.

  • 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
    An expanded version is available as a research report

Misc. Some works more remotely related to my (current or past) centers of interest.

  • 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 (preliminary version)
    arXiv:0709.0170
  • 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