Export Publications

Export the displayed publications:
Number of documents

54

Publications of Xavier Goaoc


Professor, Laboratoire d'informatique Gaspard Monge, Université Paris Est Marne-la-Vallée


Book sections2 documents

Journal articles25 documents

  • Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Shellability is NP-complete. Journal of the ACM (JACM), Association for Computing Machinery, In press. ⟨hal-02050505⟩
  • Jesús A. de Loera, Xavier Goaoc, Frédéric Meunier, Nabil Mustafa. The discrete yet ubiquitous theorems of Caratheodory, Helly, Sperner, Tucker, and Tverberg. Bulletin of the American Mathematical Society, American Mathematical Society, 2019, 56, pp.415-511. ⟨10.1090/bull/1653⟩. ⟨hal-02050466⟩
  • Boris Bukh, Xavier Goaoc. Shatter functions with polynomial growth rates. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, In press. ⟨hal-02050524⟩
  • Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, et al.. On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-type Nonembeddability Result. Israël Journal of Mathematics, The Hebrew University Magnes Press, 2017, 222 (2), pp.841-866. ⟨10.1007/s11856-017-1607-7⟩. ⟨hal-01744156⟩
  • Boris Aronov, Otfried Cheong, Michael Gene Dobbins, Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. Discrete and Computational Geometry, Springer Verlag, 2017, 57 (1), pp.104 - 124. ⟨10.1007/s00454-016-9820-4⟩. ⟨hal-01578460⟩
  • Jae-Soon Ha, Otfried Cheong, Xavier Goaoc, Jungwoo Yang. Geometric permutations of non-overlapping unit balls revisited. Computational Geometry, Elsevier, 2016, 53, pp.36-50. ⟨10.1016/j.comgeo.2015.12.003⟩. ⟨hal-01393009⟩
  • Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse. Smoothed complexity of convex hulls by witnesses and collectors. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (2), pp.101-144. ⟨10.20382/jocg.v7i2a6⟩. ⟨hal-01285120⟩
  • Xavier Goaoc, Jiří Matoušek, Pavel Paták, Zuzana Safernová, Martin Tancer. Simplifying Inclusion–Exclusion Formulas. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2015, 24 (02), pp.438 - 456. ⟨10.1017/S096354831400042X⟩. ⟨hal-01578188⟩
  • Éric Colin de Verdière, Grégory Ginot, Xavier Goaoc. Helly numbers of acyclic families. Advances in Mathematics, Elsevier, 2014, 253, pp.163-193. ⟨10.1016/j.aim.2013.11.004⟩. ⟨hal-00646166⟩
  • Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, Matthias Reitzner. The monotonicity of $f$-vectors of random polytopes. Electronic Communications in Probability, Institute of Mathematical Statistics (IMS), 2013, 18 (23), pp.1-8. ⟨10.1214/ECP.v18-2469⟩. ⟨hal-00805690⟩
  • Otfried Cheong, Xavier Goaoc, Cyril Nicaud. Set Systems and Families of Permutations with Small Traces. European Journal of Combinatorics, Elsevier, 2013, 34, pp.229-239. ⟨hal-00752064⟩
  • Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard. Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, 42 (2), pp.662-684. ⟨10.1137/100816079⟩. ⟨hal-00927100⟩
  • Otfried Cheong, Xavier Goaoc, Andreas Holmsen. Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls. Israël Journal of Mathematics, The Hebrew University Magnes Press, 2012, 190 (1), pp.213-228. ⟨https://link.springer.com/article/10.1007%2Fs11856-011-0179-1⟩. ⟨inria-00518035⟩
  • Xavier Goaoc, Stefan Koenig, Sylvain Petitjean. Pinning a Line by Balls or Ovaloids in $R^3$. Discrete and Computational Geometry, Springer Verlag, 2011, 45 (2), pp.303-320. ⟨10.1007/s00454-010-9297-5⟩. ⟨inria-00518033⟩
  • Boris Aronov, Otfried Cheong, Xavier Goaoc, Rote Günter. Lines Pinning Lines. Discrete and Computational Geometry, Springer Verlag, 2011. ⟨inria-00518028⟩
  • Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, et al.. Untangling a Planar Graph. Discrete and Computational Geometry, Springer Verlag, 2009, 42 (4), pp.542-569. ⟨10.1007/s00454-008-9130-6⟩. ⟨inria-00431408⟩
  • Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.379--398. ⟨10.1007/s00454-009-9167-1⟩. ⟨inria-00404171⟩
  • Guillaume Batog, Xavier Goaoc. Inflating balls is NP-hard. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2008. ⟨inria-00331423⟩
  • Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean. Helly-Type Theorems for Line Transversals to Disjoint Unit Balls. Discrete and Computational Geometry, Springer Verlag, 2008, 39 (1-3), pp.194-212. ⟨inria-00103856⟩
  • Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean. Line transversals to disjoint balls. Discrete and Computational Geometry, Springer Verlag, 2008, 39 (1-3), pp.158--173. ⟨10.1007/s00454-007-9016-z⟩. ⟨inria-00176198⟩
  • Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2007, 37 (2), pp.522-551. ⟨10.1137/S0097539705447116⟩. ⟨inria-00103916⟩
  • Véronique Cortier, Xavier Goaoc, Mira Lee, Na Hyeon-Suk. A note on maximally repeated sub-patterns of a point set. Discrete Mathematics, Elsevier, 2006, 306 (16), pp.1965-1968. ⟨hal-00097239⟩
  • Ciprian Borcea, Xavier Goaoc, Sylvain Lazard, Sylvain Petitjean. Common Tangents to Spheres in $R3$. Discrete and Computational Geometry, Springer Verlag, 2006, 35 (2), pp.287-300. ⟨10.1007/s00454-005-1230-y⟩. ⟨inria-00100261⟩
  • Otfried Cheong, Xavier Goaoc, Na Hyeon-Suk. Geometric Permutations of Disjoint Unit Spheres. Computational Geometry, Elsevier, 2005, 30 (3), pp.253-270. ⟨inria-00000637⟩
  • Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, et al.. The expected number of 3D visibility events is linear. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2003, 32 (6), pp.1586-1620. ⟨10.1137/S0097539702419662⟩. ⟨inria-00099810⟩

Conference papers26 documents

  • Xavier Goaoc, Andreas Holmsen, Cyril Nicaud. An experimental study of forbidden patterns in geometric permutations by combinatorial lifting. 35th International Symposium on Computational Geometry, 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.40⟩. ⟨hal-02050539⟩
  • Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Shellability is NP-complete. International Symposium on Computational Geometry, 2018, Budapest, Hungary. ⟨hal-01744101⟩
  • Boris Bukh, Xavier Goaoc, Alfredo Hubard, Matthew Trager. Consistent Sets of Lines with no Colorful Incidence. SoCG 2018 - 34thInternational Symposium on Computational Geometry, Jun 2018, Budapest, Hungary. pp.1-20. ⟨hal-01744125⟩
  • Boris Aronov, Otfried Cheong, Michael Dobbins, Xavier Goaoc. The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions. SoCG 2016, Jun 2016, Boston, United States. pp.10:1-10:16. ⟨hal-01393017⟩
  • Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, et al.. On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-type Nonembeddability Result. 31st International Symposium on Computational Geometry (SoCG’15), Jun 2015, Eindhoven, Netherlands. pp.476-490, ⟨10.4230/LIPIcs.SOCG.2015.476⟩. ⟨hal-01393019⟩
  • Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, Jan Volec. Limits of order types. Symposium on Computational Geometry 2015, Jun 2015, Eindhoven, Netherlands. pp.876, ⟨10.4230/LIPIcs.SOCG.2015.300⟩. ⟨hal-01172466⟩
  • Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner. Bounding Helly Numbers via Betti Numbers. International Symposium on Computational Geometry, 2015, Eindhoven, Netherlands. pp.507--521, ⟨10.4230/LIPIcs.SOCG.2015.507⟩. ⟨hal-01577897⟩
  • Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse. On the smoothed complexity of convex hulls. Proceedings of the 31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. pp.224-238, ⟨10.4230/LIPIcs.SOCG.2015.224⟩. ⟨hal-01144473v2⟩
  • Xavier Goaoc, Jiří Matoušek, Pavel Paták, Zuzana Safernová, Martin Tancer. Simplifying inclusion-exclusion formulas. European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. ⟨hal-00764182⟩
  • Olivier Devillers, Marc Glisse, Xavier Goaoc. Complexity Analysis of Random Geometric Structures Made Simpler. 29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, ⟨10.1145/2462356.2462362⟩. ⟨hal-00833774⟩
  • Éric Colin de Verdière, Grégory Ginot, Xavier Goaoc. Multinerves and Helly Numbers of Acyclic Families. Symposium on Computational Geometry - SoCG '12, Jun 2012, Chapel Hill, United States. pp.209-218, ⟨10.1145/2261250.2261282⟩. ⟨hal-00752073⟩
  • Guillaume Batog, Xavier Goaoc, Jean Ponce. Admissible Linear Map Models of Linear Cameras. 23rd IEEE Conference on Computer Vision and Pattern Recognition - CVPR 2010, Jun 2010, San Francisco, United States. pp.1578 - 1585, ⟨10.1109/CVPR.2010.5539784⟩. ⟨inria-00517899⟩
  • Otfried Cheong, Xavier Goaoc, Cyril Nicaud. Set Systems and Families of Permutations with Small Traces (abstract). 8th French Combinatorial Conference, 2010, France. ⟨hal-00620460⟩
  • Julien Demouth, Xavier Goaoc. Computing Direct Shadows Cast by Convex Polyhedra. 25th European Workshop on Computational Geometry - EuroCG 2009, Mar 2009, Brussels, Belgium. ⟨inria-00431544⟩
  • Otfried Cheong, Xavier Goaoc, Andreas Holmsen. Lower Bounds for Pinning Lines by Balls (Extended Abstract). European Conference on Combinatorics, Graph Theory and Applications - EuroComb 2009, Sep 2009, Bordeaux, France. pp.567-571, ⟨10.1016/j.endm.2009.07.094⟩. ⟨inria-00431437⟩
  • Xavier Goaoc, Kim Hyo-Sil, Lim Jung-Gun. There are arbitrary large minimal 2-pinning configurations. The First Asian Association for Algorithms and Computation Annual Meeting - AAAC 08, Apr 2008, Hong-Kong, China. ⟨inria-00431768⟩
  • Olivier Devillers, Jeff Erickson, Xavier Goaoc. Empty-ellipse graphs. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256. ⟨inria-00176204⟩
  • Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. Proceedings of the 24th Annual Symposium on Computational Geometry, Jun 2008, College Park, Maryland, United States. pp.120--128. ⟨inria-00331435⟩
  • Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean. Line transversals to disjoint balls. 23rd Annual ACM Symposium on Computational Geometry 2007 - SoCG'07, 2007, Gyeongju, South Korea. pp.245-254, ⟨10.1145/1247069.1247115⟩. ⟨inria-00176201⟩
  • Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Alexander Wolff. Moving vertices to make drawings plane. 15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. pp.101-112, ⟨10.1007/978-3-540-77537-9_13⟩. ⟨inria-00181775⟩
  • Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean. Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract). European Workshop on Computational Geometry, Mar 2006, Delphi, Greece. pp.87--89. ⟨inria-00189019⟩
  • Otfried Cheong, Xavier Goaoc, Andreas Holmsen. Hadwiger and Helly-type theorems for disjoint unit spheres in R3. 21st Annual ACM Symposium on Computational Geometry 2005 (SoCG'05 ), Jun 2005, Pisa, Italy. pp.10-15, ⟨10.1145/1064092.1064097⟩. ⟨inria-00000206⟩
  • Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D. Proceedings of the 20th Annual Symposium on Computational Geometry, Jun 2004, Brooklyn, NY, United States. pp.46 - 55, ⟨10.1145/997817.997827⟩. ⟨inria-00103995⟩
  • Otfried Cheong, Xavier Goaoc, Na Hyeon-Suk. Disjoint Unit Spheres Admit At Most Two Line Transversals. 11th Annual European Symposium on Algorithms - ESA 2003, Sep 2003, Budapest, Hungary. pp.127-135, ⟨10.1007/b13632⟩. ⟨inria-00103857⟩
  • Helmut Alt, Marc Glisse, Xavier Goaoc. On the worst-case complexity of the silhouette of a polytope. 15th Canadian Conference on Computational Geometry - CCCG 2003, 2003, Halifax, Canada, 4 p. ⟨inria-00099478⟩
  • Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, et al.. On the Number of Lines Tangent to Four Convex Polyhedra. 14th Canadian Conference on Computational Geometry - CCCG'02, 2002, Lethbridge, Canada. ⟨inria-00099449⟩

Habilitation à diriger des recherches1 document

  • Xavier Goaoc. Transversal Helly numbers, pinning theorems and projection of simplicial complexes. Computational Geometry [cs.CG]. Université Henri Poincaré - Nancy I, 2011. ⟨tel-00650204v2⟩