Accéder directement au contenu

Xavier Goaoc

61
Documents

Présentation

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

Publications

Convexité combinatoire

Xavier Goaoc
Informatique Mathématique : Une photographie en 2020, CNRS Éditions, 2020, 978-2271134134
Chapitre d'ouvrage hal-03130356v1

Bounding Helly Numbers via Betti Numbers

Xavier Goaoc , Pavel Paták , Zuzana Patáková , Martin Tancer , Uli Wagner
Martin Loebl, Jaroslav Nešetřil, Robin Thomas. A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp.407-447, 2017, ⟨10.1007/978-3-319-44479-6_17⟩
Chapitre d'ouvrage hal-01744167v1
Image document

Some Discrete Properties of the Space of Line Transversals to Disjoint Balls

Xavier Goaoc
I. Emiris, F. Sottile and T. Theobald. Non-linear Computational Geometry, 151, Springer New York, pp.51-84, 2008, The IMA Volumes in Mathematics and its Applications, 978-1-4419-0998-5 (Print) 978-1-4419-0999-2 (Online). ⟨10.1007/978-1-4419-0999-2_3⟩
Chapitre d'ouvrage inria-00335946v1

Some New Results on Geometric Transversals

Otfried Cheong , Xavier Goaoc , Andreas Holmsen
Discrete and Computational Geometry, inPress, ⟨10.1007/s00454-023-00573-2⟩
Article dans une revue hal-04293155v1

Convex Hulls of Random Order Types

Xavier Goaoc , Emo Welzl
Journal of the ACM (JACM), 2023, 70 (1), pp.1-47. ⟨10.1145/3570636⟩
Article dans une revue hal-03831575v1

An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

Xavier Goaoc , Andreas Holmsen , Cyril Nicaud
Journal of Computational Geometry, 2021, Special Issue of Selected Papers from SoCG 2019, 11 (2), pp.131-161. ⟨10.20382/jocg.v11i2a6⟩
Article dans une revue hal-03152958v1

Random polytopes and the wet part for arbitrary probability distributions

Imre Bárány , Matthieu Fradelizi , Xavier Goaoc , Alfredo Hubard , Günter Rote
Annales Henri Lebesgue, 2020, 3, pp.701-715. ⟨10.5802/ahl.44⟩
Article dans une revue hal-02937527v1

The discrete yet ubiquitous theorems of Caratheodory, Helly, Sperner, Tucker, and Tverberg

Jesús A. de Loera , Xavier Goaoc , Frédéric Meunier , Nabil Mustafa
Bulletin of the American Mathematical Society, 2019, 56, pp.415-511. ⟨10.1090/bull/1653⟩
Article dans une revue hal-02050466v1

Shellability is NP-complete

Xavier Goaoc , Pavel Paták , Zuzana Patáková , Martin Tancer , Uli Wagner
Journal of the ACM (JACM), 2019, 66 (3), pp.1-18. ⟨10.1145/3314024⟩
Article dans une revue hal-02050505v1

Shatter functions with polynomial growth rates

Boris Bukh , Xavier Goaoc
SIAM Journal on Discrete Mathematics, 2019, 33 (2), pp.784-794. ⟨10.1137/17M1113680⟩
Article dans une revue hal-02050524v1

On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-type Nonembeddability Result

Xavier Goaoc , Isaac Mabillard , Pavel Paták , Zuzana Patáková , Martin Tancer
Israel Journal of Mathematics, 2017, 222 (2), pp.841-866. ⟨10.1007/s11856-017-1607-7⟩
Article dans une revue hal-01744156v1

The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Boris Aronov , Otfried Cheong , Michael Gene Dobbins , Xavier Goaoc
Discrete and Computational Geometry, 2017, 57 (1), pp.104 - 124. ⟨10.1007/s00454-016-9820-4⟩
Article dans une revue hal-01578460v1
Image document

Smoothed complexity of convex hulls by witnesses and collectors

Olivier Devillers , Marc Glisse , Xavier Goaoc , Rémy Thomasse
Journal of Computational Geometry, 2016, 7 (2), pp.101-144. ⟨10.20382/jocg.v7i2a6⟩
Article dans une revue hal-01285120v1
Image document

Geometric permutations of non-overlapping unit balls revisited

Jae-Soon Ha , Otfried Cheong , Xavier Goaoc , Jungwoo Yang
Computational Geometry, 2016, 53, pp.36-50. ⟨10.1016/j.comgeo.2015.12.003⟩
Article dans une revue hal-01393009v1

Simplifying Inclusion–Exclusion Formulas

Xavier Goaoc , Jiří Matoušek , Pavel Paták , Zuzana Safernová , Martin Tancer
Combinatorics, Probability and Computing, 2015, 24 (02), pp.438 - 456. ⟨10.1017/S096354831400042X⟩
Article dans une revue hal-01578188v1
Image document

Helly numbers of acyclic families

Éric Colin de Verdière , Grégory Ginot , Xavier Goaoc
Advances in Mathematics, 2014, 253, pp.163-193. ⟨10.1016/j.aim.2013.11.004⟩
Article dans une revue hal-00646166v1
Image document

The monotonicity of $f$-vectors of random polytopes

Olivier Devillers , Marc Glisse , Xavier Goaoc , Guillaume Moroz , Matthias Reitzner
Electronic Communications in Probability, 2013, 18 (23), pp.1-8. ⟨10.1214/ECP.v18-2469⟩
Article dans une revue hal-00805690v1
Image document

Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization

Xavier Goaoc , Hyo-Sil Kim , Sylvain Lazard
SIAM Journal on Computing, 2013, 42 (2), pp.662-684. ⟨10.1137/100816079⟩
Article dans une revue hal-00927100v1
Image document

Set Systems and Families of Permutations with Small Traces

Otfried Cheong , Xavier Goaoc , Cyril Nicaud
European Journal of Combinatorics, 2013, 34, pp.229-239
Article dans une revue hal-00752064v1

Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls

Otfried Cheong , Xavier Goaoc , Andreas Holmsen
Israel Journal of Mathematics, 2012, 190 (1), pp.213-228
Article dans une revue inria-00518035v1

Pinning a Line by Balls or Ovaloids in $R^3$

Xavier Goaoc , Stefan Koenig , Sylvain Petitjean
Discrete and Computational Geometry, 2011, 45 (2), pp.303-320. ⟨10.1007/s00454-010-9297-5⟩
Article dans une revue inria-00518033v1

Lines Pinning Lines

Boris Aronov , Otfried Cheong , Xavier Goaoc , Rote Günter
Discrete and Computational Geometry, 2011
Article dans une revue inria-00518028v1
Image document

Helly-type theorems for approximate covering

Julien Demouth , Olivier Devillers , Marc Glisse , Xavier Goaoc
Discrete and Computational Geometry, 2009, 42 (3), pp.379--398. ⟨10.1007/s00454-009-9167-1⟩
Article dans une revue inria-00404171v1

Untangling a Planar Graph

Xavier Goaoc , Jan Kratochvil , Yoshio Okamoto , Chan-Su Shin , Andreas Spillner
Discrete and Computational Geometry, 2009, 42 (4), pp.542-569. ⟨10.1007/s00454-008-9130-6⟩
Article dans une revue inria-00431408v1
Image document

Line transversals to disjoint balls

Ciprian Borcea , Xavier Goaoc , Sylvain Petitjean
Discrete and Computational Geometry, 2008, 39 (1-3), pp.158--173. ⟨10.1007/s00454-007-9016-z⟩
Article dans une revue inria-00176198v1
Image document

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

Otfried Cheong , Xavier Goaoc , Andreas Holmsen , Sylvain Petitjean
Discrete and Computational Geometry, 2008, 39 (1-3), pp.194-212
Article dans une revue inria-00103856v1
Image document

Inflating balls is NP-hard

Guillaume Batog , Xavier Goaoc
International Journal of Computational Geometry and Applications, 2008
Article dans une revue inria-00331423v1
Image document

Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra

Hervé Brönnimann , Olivier Devillers , Vida Dujmovic , Hazel Everett , Marc Glisse
SIAM Journal on Computing, 2007, 37 (2), pp.522-551. ⟨10.1137/S0097539705447116⟩
Article dans une revue inria-00103916v1
Image document

A note on maximally repeated sub-patterns of a point set

Véronique Cortier , Xavier Goaoc , Mira Lee , Na Hyeon-Suk
Discrete Mathematics, 2006, 306 (16), pp.1965-1968. ⟨10.1016/j.disc.2006.03.045⟩
Article dans une revue hal-00097239v1
Image document

Common Tangents to Spheres in $R3$

Ciprian Borcea , Xavier Goaoc , Sylvain Lazard , Sylvain Petitjean
Discrete and Computational Geometry, 2006, 35 (2), pp.287-300. ⟨10.1007/s00454-005-1230-y⟩
Article dans une revue inria-00100261v1
Image document

Geometric Permutations of Disjoint Unit Spheres

Otfried Cheong , Xavier Goaoc , Na Hyeon-Suk
Computational Geometry, 2005, 30 (3), pp.253-270
Article dans une revue inria-00000637v1
Image document

The expected number of 3D visibility events is linear

Olivier Devillers , Vida Dujmovic , Hazel Everett , Xavier Goaoc , Sylvain Lazard
SIAM Journal on Computing, 2003, 32 (6), pp.1586-1620. ⟨10.1137/S0097539702419662⟩
Article dans une revue inria-00099810v1

A Stepping-Up Lemma for Topological Set Systems

Xavier Goaoc , Andreas Holmsen , Zuzana Patáková
SoCG 2021 - 37th International Symposium on Computational Geometry, Jun 2021, Buffalo/virtual, United States. pp.40:1--40:17, ⟨10.4230/LIPIcs.SoCG.2021.40⟩
Communication dans un congrès hal-03341599v1

Convex Hulls of Random Order Types

Xavier Goaoc , Emo Welzl
SoCG 2020 - 36th International Symposium on Computational Geometry, Jun 2020, Zürich / Virtual, Switzerland. pp.49:1--49:15, ⟨10.4230/LIPIcs.SoCG.2020.49⟩
Communication dans un congrès hal-02879289v1

An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

Xavier Goaoc , Andreas Holmsen , Cyril Nicaud
35th International Symposium on Computational Geometry, 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.40⟩
Communication dans un congrès hal-02050539v1

Consistent Sets of Lines with no Colorful Incidence

Boris Bukh , Xavier Goaoc , Alfredo Hubard , Matthew Trager
SoCG 2018 - 34thInternational Symposium on Computational Geometry, Jun 2018, Budapest, Hungary. pp.1-20
Communication dans un congrès hal-01744125v1

Shellability is NP-complete

Xavier Goaoc , Pavel Paták , Zuzana Patáková , Martin Tancer , Uli Wagner
International Symposium on Computational Geometry, 2018, Budapest, Hungary. ⟨10.4230/LIPIcs.SoCG.2018.41⟩
Communication dans un congrès hal-01744101v1
Image document

The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions

Boris Aronov , Otfried Cheong , Michael Gene Dobbins , Xavier Goaoc
SoCG 2016, Jun 2016, Boston, United States. pp.10:1-10:16
Communication dans un congrès hal-01393017v1

Limits of order types

Xavier Goaoc , Alfredo Hubard , Rémi de Joannis de Verclos , Jean-Sébastien Sereni , Jan Volec
Symposium on Computational Geometry 2015, Jun 2015, Eindhoven, Netherlands. pp.876, ⟨10.4230/LIPIcs.SOCG.2015.300⟩
Communication dans un congrès hal-01172466v1
Image document

On the smoothed complexity of convex hulls

Olivier Devillers , Marc Glisse , Xavier Goaoc , Rémy Thomasse
Proceedings of the 31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. pp.224-238, ⟨10.4230/LIPIcs.SOCG.2015.224⟩
Communication dans un congrès hal-01144473v2

Bounding Helly Numbers via Betti Numbers

Xavier Goaoc , Pavel Paták , Zuzana Patáková , Martin Tancer , Uli Wagner
International Symposium on Computational Geometry, 2015, Eindhoven, Netherlands. pp.507--521, ⟨10.4230/LIPIcs.SOCG.2015.507⟩
Communication dans un congrès hal-01577897v1
Image document

On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-type Nonembeddability Result

Xavier Goaoc , Isaac Mabillard , Pavel Paták , Zuzana Patáková , Martin Tancer
31st International Symposium on Computational Geometry (SoCG’15), Jun 2015, Eindhoven, Netherlands. pp.476-490, ⟨10.4230/LIPIcs.SOCG.2015.476⟩
Communication dans un congrès hal-01393019v1

Simplifying inclusion-exclusion formulas

Xavier Goaoc , Jiří Matoušek , Pavel Paták , Zuzana Safernová , Martin Tancer
European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy
Communication dans un congrès hal-00764182v1
Image document

Complexity Analysis of Random Geometric Structures Made Simpler

Olivier Devillers , Marc Glisse , Xavier Goaoc
29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, ⟨10.1145/2462356.2462362⟩
Communication dans un congrès hal-00833774v1
Image document

Multinerves and Helly Numbers of Acyclic Families

Éric Colin de Verdière , Grégory Ginot , Xavier Goaoc
Symposium on Computational Geometry - SoCG '12, Jun 2012, Chapel Hill, United States. pp.209-218, ⟨10.1145/2261250.2261282⟩
Communication dans un congrès hal-00752073v1

Set Systems and Families of Permutations with Small Traces (abstract)

Otfried Cheong , Xavier Goaoc , Cyril Nicaud
8th French Combinatorial Conference, 2010, France
Communication dans un congrès hal-00620460v1
Image document

Admissible Linear Map Models of Linear Cameras

Guillaume Batog , Xavier Goaoc , Jean Ponce
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⟩
Communication dans un congrès inria-00517899v1
Image document

Lower Bounds for Pinning Lines by Balls (Extended Abstract)

Otfried Cheong , Xavier Goaoc , Andreas Holmsen
European Conference on Combinatorics, Graph Theory and Applications - EuroComb 2009, Sep 2009, Bordeaux, France. pp.567-571, ⟨10.1016/j.endm.2009.07.094⟩
Communication dans un congrès inria-00431437v1
Image document

Computing Direct Shadows Cast by Convex Polyhedra

Julien Demouth , Xavier Goaoc
25th European Workshop on Computational Geometry - EuroCG 2009, Mar 2009, Brussels, Belgium
Communication dans un congrès inria-00431544v1
Image document

Empty-ellipse graphs

Olivier Devillers , Jeff Erickson , Xavier Goaoc
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256
Communication dans un congrès inria-00176204v1
Image document

Helly-type theorems for approximate covering

Julien Demouth , Olivier Devillers , Marc Glisse , Xavier Goaoc
SoCG 2008 - 24th Annual Symposium on Computational Geometry, Jun 2008, College Park, Maryland, United States. pp.120--128
Communication dans un congrès inria-00331435v1
Image document

There are arbitrary large minimal 2-pinning configurations

Xavier Goaoc , Kim Hyo-Sil , Lim Jung-Gun
The First Asian Association for Algorithms and Computation Annual Meeting - AAAC 08, Apr 2008, Hong-Kong, China
Communication dans un congrès inria-00431768v1
Image document

Line transversals to disjoint balls

Ciprian Borcea , Xavier Goaoc , Sylvain Petitjean
23rd Annual ACM Symposium on Computational Geometry 2007 - SoCG'07, 2007, Gyeongju, South Korea. pp.245-254, ⟨10.1145/1247069.1247115⟩
Communication dans un congrès inria-00176201v1
Image document

Moving vertices to make drawings plane

Xavier Goaoc , Jan Kratochvil , Yoshio Okamoto , Chan-Su Shin , Alexander Wolff
15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. pp.101-112, ⟨10.1007/978-3-540-77537-9_13⟩
Communication dans un congrès inria-00181775v1
Image document

Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract)

Otfried Cheong , Xavier Goaoc , Andreas Holmsen , Sylvain Petitjean
European Workshop on Computational Geometry, Mar 2006, Delphi, Greece. pp.87--89
Communication dans un congrès inria-00189019v1
Image document

Hadwiger and Helly-type theorems for disjoint unit spheres in R3

Otfried Cheong , Xavier Goaoc , Andreas Holmsen
21st Annual ACM Symposium on Computational Geometry 2005 (SoCG'05 ), Jun 2005, Pisa, Italy. pp.10-15, ⟨10.1145/1064092.1064097⟩
Communication dans un congrès inria-00000206v1
Image document

The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D

Hervé Brönnimann , Olivier Devillers , Vida Dujmovic , Hazel Everett , Marc Glisse
Proceedings of the 20th Annual Symposium on Computational Geometry, Jun 2004, Brooklyn, NY, United States. pp.46 - 55, ⟨10.1145/997817.997827⟩
Communication dans un congrès inria-00103995v1
Image document

On the worst-case complexity of the silhouette of a polytope

Helmut Alt , Marc Glisse , Xavier Goaoc
15th Canadian Conference on Computational Geometry - CCCG 2003, 2003, Halifax, Canada, 4 p
Communication dans un congrès inria-00099478v1
Image document

Disjoint Unit Spheres Admit At Most Two Line Transversals

Otfried Cheong , Xavier Goaoc , Na Hyeon-Suk
11th Annual European Symposium on Algorithms - ESA 2003, Sep 2003, Budapest, Hungary. pp.127-135, ⟨10.1007/b13632⟩
Communication dans un congrès inria-00103857v1
Image document

On the Number of Lines Tangent to Four Convex Polyhedra

Hervé Brönnimann , Olivier Devillers , Vida Dujmovic , Hazel Everett , Marc Glisse
14th Canadian Conference on Computational Geometry - CCCG'02, 2002, Lethbridge, Canada
Communication dans un congrès inria-00099449v1
Image document

Transversal Helly numbers, pinning theorems and projection of simplicial complexes

Xavier Goaoc
Computational Geometry [cs.CG]. Université Henri Poincaré - Nancy I, 2011
HDR tel-00650204v2