Publications of Xavier Goaoc

2016

Journal articles

vignette.png
titre
Smoothed complexity of convex hulls by witnesses and collectors
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse
article
Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (2), pp.101-144. <http://jocg.org/v7n2p6>. <10.20382/jocg.v7i2a6>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01285120/file/265-1014-1-PB.pdf BibTex

2015

Conference papers

vignette.png
titre
On the smoothed complexity of convex hulls
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse
article
31st International Symposium on Computational Geometry, Jun 2015, Eindhoven, Netherlands. Lipics, 2015, <http://www.win.tue.nl/SoCG2015/>. <10.4230/LIPIcs.SOCG.2015.224>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01144473/file/socg-final.pdf BibTex
titre
Limits of order types
auteur
Xavier Goaoc, Alfredo Hubard, Rémi De Joannis de Verclos, Jean-Sébastien Sereni, Jan Volec
article
Janos Pach, Larse Arge. Symposium on Computational Geometry 2015, Jun 2015, Eindhoven, Netherlands. 34, pp.876, 2015, Symposium on Computational Geometry 2015: Eindhoven, The Netherlands. <10.4230/LIPIcs.SOCG.2015.300>
Accès au bibtex
BibTex

Reports

vignette.png
titre
Smoothed complexity of convex hulls by witnesses and collectors
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc, Rémy Thomasse
article
[Research Report] 8787, INRIA. 2015, pp.41
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-01214021/file/RR-8787.pdf BibTex

2013

Journal articles

titre
Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization
auteur
Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard
article
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, 42 (2), pp.662-684. <10.1137/100816079>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00927100/file/viapoints_final.pdf BibTex
titre
The monotonicity of $f$-vectors of random polytopes
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, Matthias Reitzner
article
Electronic Communications in Probability, Institute of Mathematical Statistics (IMS), 2013, 18 (23), pp.1-8. <10.1214/ECP.v18-2469>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00805690/file/ecp.pdf BibTex
titre
Set Systems and Families of Permutations with Small Traces
auteur
Otfried Cheong, Xavier Goaoc, Cyril Nicaud
article
European Journal of Combinatorics, Elsevier, 2013, 34, pp.229-239. <http://www.sciencedirect.com/science/article/pii/S0195669812001072>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00752064/file/SetSystemsSmallTraces.pdf BibTex

Conference papers

titre
Simplifying inclusion-exclusion formulas
auteur
Xavier Goaoc, Jiří Matoušek, Pavel Paták, Zuzana Safernová, Martin Tancer
article
European Conference on Combinatorics, Graph Theory and Applications, Sep 2013, Pisa, Italy. 2013
Accès au bibtex
https://arxiv.org/pdf/1207.2591 BibTex
vignette.jpg
titre
Complexity Analysis of Random Geometric Structures Made Simpler
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc
article
29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, 2013, <10.1145/2462356.2462362>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00833774/file/hal-version.pdf BibTex

2012

Conference papers

titre
Multinerves and Helly Numbers of Acyclic Families
auteur
Éric Colin De Verdière, Grégory Ginot, Xavier Goaoc
article
Symposium on Computational Geometry - SoCG '12, Jun 2012, Chapel Hill, United States. ACM, pp.209-218, 2012, <http://dl.acm.org/citation.cfm?doid=2261250.2261282>. <10.1145/2261250.2261282>
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00752073/file/multinerve-socg.pdf BibTex

Reports

titre
Complexity analysis of random geometric structures made simpler
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc
article
[Research Report] RR-8168, INRIA. 2012
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00761171/file/RR-8168.pdf BibTex
titre
The monotonicity of f-vectors of random polytopes
auteur
Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, Matthias Reitzner
article
[Research Report] RR-8154, INRIA. 2012, pp.10
Accès au texte intégral et bibtex
https://hal.inria.fr/hal-00758686/file/RR-8154.pdf BibTex

2011

Journal articles

titre
Pinning a Line by Balls or Ovaloids in $R^3$
auteur
Xavier Goaoc, Stefan Koenig, Sylvain Petitjean
article
Discrete and Computational Geometry, Springer Verlag, 2011, 45 (2), pp.303-320. <10.1007/s00454-010-9297-5>
Accès au bibtex
BibTex
titre
Lines Pinning Lines
auteur
Boris Aronov, Otfried Cheong, Xavier Goaoc, Rote Günter
article
Discrete and Computational Geometry, Springer Verlag, 2011
Accès au bibtex
BibTex

Habilitation à diriger des recherches

titre
Transversal Helly numbers, pinning theorems and projection of simplicial complexes
auteur
Xavier Goaoc
article
Computational Geometry [cs.CG]. Université Henri Poincaré - Nancy I, 2011
Accès au texte intégral et bibtex
https://tel.archives-ouvertes.fr/tel-00650204/file/thesis.pdf BibTex

2010

Journal articles

titre
Lower Bounds to Helly Numbers of Line Transversals to Disjoint Congruent Balls
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen
article
Israël Journal of Mathematics, The Hebrew University Magnes Press, 2010
Accès au bibtex
BibTex

Conference papers

titre
Admissible Linear Map Models of Linear Cameras
auteur
Guillaume Batog, Xavier Goaoc, Jean Ponce
article
23rd IEEE Conference on Computer Vision and Pattern Recognition - CVPR 2010, Jun 2010, San Francisco, United States. IEEE, pp.1578 - 1585, 2010, 2010 IEEE Conference on Computer Vision and Pattern Recognition. <10.1109/CVPR.2010.5539784>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00517899/file/admap.pdf BibTex
titre
Set Systems and Families of Permutations with Small Traces (abstract)
auteur
Otfried Cheong, Xavier Goaoc, Cyril Nicaud
article
8th French Combinatorial Conference, 2010, France
Accès au bibtex
BibTex

Reports

titre
Bounded-Curvature Shortest Paths through a Sequence of Points
auteur
Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard
article
[Research Report] RR-7465, INRIA. 2010, pp.53
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00539957/file/RR-7465.pdf BibTex

2009

Journal articles

titre
Untangling a Planar Graph
auteur
Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, Alexander Wolff
article
Discrete and Computational Geometry, Springer Verlag, 2009, 42 (4), pp.542-569. <http://www.springerlink.com/content/p2632528711262jt/?p=ba71c126f1a64943b1fa0d43a714d9e1&pi=33>. <10.1007/s00454-008-9130-6>
Accès au bibtex
BibTex
titre
Helly-type theorems for approximate covering
auteur
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc
article
Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.379--398. <10.1007/s00454-009-9167-1>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00404171/file/appcover.pdf BibTex

Conference papers

titre
Lower Bounds for Pinning Lines by Balls (Extended Abstract)
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen
article
European Conference on Combinatorics, Graph Theory and Applications - EuroComb 2009, Sep 2009, Bordeaux, France. Elsevier, 34, pp.567-571, 2009, Electronic Notes in Discrete Mathematics (ENDM); European Conference on Combinatorics, Graph Theory and Applications - EuroComb 2009. <http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B75GV-4WWHRTR-3C&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=79af951d447239bd59b51c623ade6428>. <10.1016/j.endm.2009.07.094>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00431437/file/Pinning-Eurocomb09.pdf BibTex
titre
Computing Direct Shadows Cast by Convex Polyhedra
auteur
Julien Demouth, Xavier Goaoc
article
25th European Workshop on Computational Geometry - EuroCG 2009, Mar 2009, Brussels, Belgium. 2009
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00431544/file/Shadows-abstract.pdf BibTex

Reports

titre
Set Systems and Families of Permutations with Small Traces
auteur
Otfried Cheong, Xavier Goaoc, Cyril Nicaud
article
[Research Report] RR-7154, INRIA. 2009, pp.14
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00441376/file/RR-7154.pdf BibTex
titre
Lower Bounds for Pinning Lines by Balls
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen
article
[Research Report] RR-6961, INRIA. 2009, pp.12
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00395837/file/RR-6961.pdf BibTex
titre
The Effect of Noise on the Number of Extreme Points
auteur
Dominique Attali, Olivier Devillers, Xavier Goaoc
article
[Research Report] RR-7134, INRIA. 2009, pp.24
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00438409/file/RR-7134.pdf BibTex

2008

Journal articles

titre
Helly-Type Theorems for Line Transversals to Disjoint Unit Balls
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean
article
Discrete and Computational Geometry, Springer Verlag, 2008, 39 (1-3), pp.194-212
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00103856/file/Helly-for-transversals.pdf BibTex
titre
Line transversals to disjoint balls
auteur
Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean
article
Discrete and Computational Geometry, Springer Verlag, 2008, 39 (1-3), pp.158--173. <10.1007/s00454-007-9016-z>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00176198/file/Cone-journal.pdf BibTex
titre
Inflating balls is NP-hard
auteur
Guillaume Batog, Xavier Goaoc
article
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2008
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00331423/file/Shadock.pdf BibTex

Conference papers

titre
Helly-type theorems for approximate covering
auteur
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc
article
Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG '08, Jun 2008, Washington, United States. ACM, pp.120--128, 2008
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00331435/file/AppCovering.pdf BibTex
titre
There are arbitrary large minimal 2-pinning configurations
auteur
Xavier Goaoc, Kim Hyo-Sil, Lim Jung-Gun
article
The First Asian Association for Algorithms and Computation Annual Meeting - AAAC 08, Apr 2008, Hong-Kong, China. 2008
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00431768/file/2-pinning.pdf BibTex
titre
Empty-ellipse graphs
auteur
Olivier Devillers, Jeff Erickson, Xavier Goaoc
article
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 2008, San Francisco, United States. pp.1249--1256, 2008
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00176204/file/empty-ellipse-soda08.pdf BibTex

Book sections

titre
Some Discrete Properties of the Space of Line Transversals to Disjoint Balls
auteur
Xavier Goaoc
article
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>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00335946/file/Survey-Transversals-to-Balls.pdf BibTex

2007

Journal articles

titre
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra
auteur
Hervé Bronnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides
article
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2007, 37 (2), pp.522-551. <10.1137/S0097539705447116>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00103916/file/SIAM_final.pdf BibTex

Conference papers

titre
Moving vertices to make drawings plane
auteur
Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Alexander Wolff
article
15th International Symposium on Graph Drawing, Sep 2007, Sydney, Australia. Springer, 4875/2008, pp.101-112, 2007, Lecture Notes in Computer Science; Graph Drawing. <http://www.springerlink.com/content/515132482g137207/>. <10.1007/978-3-540-77537-9_13>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00181775/file/Vertex-move-gd07.pdf BibTex
titre
Line transversals to disjoint balls
auteur
Ciprian Borcea, Xavier Goaoc, Sylvain Petitjean
article
23rd Annual ACM Symposium on Computational Geometry 2007 - SoCG'07, 2007, Gyeongju, South Korea. ACM Press, pp.245-254, 2007, Proceedings of the twenty-third annual symposium on Computational geometry. <10.1145/1247069.1247115>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00176201/file/Cone-socg07.pdf BibTex

Reports

titre
Helly-type theorems for approximate covering
auteur
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc
article
[Research Report] RR-6342, INRIA. 2007, pp.12
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00179277/file/RR.pdf BibTex
titre
Random sampling of a cylinder yields a not so nasty Delaunay triangulation
auteur
Olivier Devillers, Xavier Goaoc
article
[Research Report] RR-6323, INRIA. 2007, pp.10
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00179313/file/RR.pdf BibTex

2006

Journal articles

titre
Common Tangents to Spheres in $R3$
auteur
Ciprian Borcea, Xavier Goaoc, Sylvain Lazard, Sylvain Petitjean
article
Discrete and Computational Geometry, Springer Verlag, 2006, 35 (2), pp.287-300. <10.1007/s00454-005-1230-y>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00100261/file/DCG_4balls_revised.pdf BibTex
titre
A note on maximally repeated sub-patterns of a point set
auteur
Véronique Cortier, Xavier Goaoc, Mira Lee, Na Hyeon-Suk
article
Discrete Mathematics, Elsevier, 2006, 306 (16), pp.1965-1968
Accès au texte intégral et bibtex
https://hal.archives-ouvertes.fr/hal-00097239/file/Repeated-sub-patterns.pdf BibTex

Conference papers

titre
Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract)
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean
article
Ioannis Emiris, Menelaos Karavelas, Leonidas Palios. European Workshop on Computational Geometry, Mar 2006, Delphi, Greece. pp.87--89, 2006, Twenty-second European Workshop on Computational Geometry - Delphi, Greece - March 27–29, 2006
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00189019/file/extended-abstract.pdf BibTex

2005

Journal articles

titre
Geometric Permutations of Disjoint Unit Spheres
auteur
Otfried Cheong, Xavier Goaoc, Na Hyeon-Suk
article
Computational Geometry, Elsevier, 2005, 30 (3), pp.253-270
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00000637/file/GP-disjoint-unit-spheres.pdf BibTex

Conference papers

titre
Hadwiger and Helly-type theorems for disjoint unit spheres in R3
auteur
Otfried Cheong, Xavier Goaoc, Andreas Holmsen
article
21st Annual ACM Symposium on Computational Geometry 2005 (SoCG'05 ), Jun 2005, Pisa, Italy. ACM Press, pp.10-15, 2005, Proceedings of the twenty-first annual symposium on Computational geometry. <10.1145/1064092.1064097>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00000206/file/Helly-type-transversals-socg05.pdf BibTex

Reports

titre
A note on maximally repeated sub-patterns of a point set
auteur
Véronique Cortier, Xavier Goaoc, Mira Lee, Hyeon-Suk Na
article
[Research Report] RR-5773, INRIA. 2005, pp.5
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00070247/file/RR-5773.pdf BibTex
titre
On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra
auteur
Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides
article
[Research Report] RR-5671, INRIA. 2005
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00071226/file/RR-5671.pdf BibTex

2004

Conference papers

titre
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D
auteur
Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides
article
Symposium on Computational Geometry - SoCG'2004, Jun 2004, Brooklyn, NY, United States. ACM, pp.46 - 55, 2004, <10.1145/997817.997827>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00103995/file/p135-lazard.pdf BibTex

Other publications

titre
On Tangents to Quadric Surfaces
auteur
Ciprian Borcea, Xavier Goaoc, Sylvain Lazard, Sylvain Petitjean
article
Manuscript. 2004
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00431701/file/Baskets.pdf BibTex

Reports

titre
Common Tangents to Spheres in R^3
auteur
Ciprian Borcea, Xavier Goaoc, Sylvain Lazard, Sylvain Petitjean
article
[Research Report] RR-5325, INRIA. 2004, pp.16
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00070675/file/RR-5325.pdf BibTex

2003

Journal articles

titre
The expected number of 3D visibility events is linear
auteur
Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sylvain Petitjean
article
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2003, 32 (6), pp.1586-1620. <10.1137/S0097539702419662>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00099810/file/SIAM-revised.pdf BibTex

Conference papers

titre
Disjoint Unit Spheres Admit At Most Two Line Transversals
auteur
Otfried Cheong, Xavier Goaoc, Na Hyeon-Suk
article
11th Annual European Symposium on Algorithms - ESA 2003, Sep 2003, Budapest, Hungary. Springer, 2832, pp.127-135, 2003, Lecture Notes in Computer Science; Algorithms - ESA 2003. <10.1007/b13632>
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00103857/file/geometric-permutations-esa03.pdf BibTex
titre
On the worst-case complexity of the silhouette of a polytope
auteur
Helmut Alt, Marc Glisse, Xavier Goaoc
article
15th Canadian Conference on Computational Geometry - CCCG 2003, 2003, Halifax, Canada, 4 p, 2003
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00099478/file/A03-R-081.pdf BibTex

Reports

titre
Disjoint Unit Spheres admit at most two Line Transversals
auteur
Otfried Cheong, Xavier Goaoc, Hyeon-Suk Na
article
[Research Report] RR-4854, INRIA. 2003
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00071729/file/RR-4854.pdf BibTex

2002

Conference papers

titre
On the Number of Lines Tangent to Four Convex Polyhedra
auteur
Hervé Brönnimann, Olivier Devillers, Vida Dujmovic, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sue Whitesides
article
14th Canadian Conference on Computational Geometry - CCCG'02, 2002, Lethbridge, Canada, 2002
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00099449/file/A02-R-268.pdf BibTex

Reports

titre
The expected number of 3D visibility events is linear
auteur
Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, Sylvain Petitjean
article
[Research Report] RR-4671, INRIA. 2002
Accès au texte intégral et bibtex
https://hal.inria.fr/inria-00071914/file/RR-4671.pdf BibTex