Publications

Authors appear in alphabetic order of names, as usual in computational geometry. You can also consult my publication list in HAL.

Submitted

Pinning a Line by Balls or Ovaloids in R³ (pdf)
X. Goaoc, S. Konig and S. Petitjean

Lines Pinning Lines (arXiv, pdf)
B. Aronov, O. Cheong, X. Goaoc and G. Rote.

The Effect of Noise on The Number of Extreme Points (research report)
D. Attali, O. Devillers and X. Goaoc.

Bounded-Curvature Shortest Path Through a Sequence of Points (manuscript)
X. Goaoc, H.-S. Kim and S. Lazard.

Set Systems and Families of Permutations with Small Traces (arXiv, research report)
O. Cheong, X. Goaoc and C. Nicaud.

Lower Bounds for Pinning Lines by Balls (arXiv, research report)
O. Cheong, X. Goaoc and A. Holmsen.

Book chapter

Some Discrete Properties of the Space of Line Transversals to Disjoint Balls (pdf)
X. Goaoc.
Non-linear Computational Geometry, IMA Volume Series 151: 51--84, 2009.

Journal articles

Inflating balls is NP-hard (pdf)
G. Batog and X. Goaoc.
To appear in the International Journal of Computational Geometry and Applications.

Untangling a Planar Graph (article, arXiv)
X. Goaoc, J. Kratochvil, Y. Okamoto, C.-S. Shin, A. Spillner and A. Wolff.
Discrete and Computational Geometry 42(4): 542--569, 2009.

Helly-type theorems for approximate covering (article, pdf)
J. Demouth, O. Devillers, M. Glisse and X. Goaoc.
Discrete and Computational Geometry 42(3): 379--398, 2009 (SCG'08 special issue).

Line transversals to disjoint balls (article, arxiv, pdf)
C. Borcea, X. Goaoc and S. Petitjean.
Discrete and Computational Geometry 39(1-3): 158--173, 2008 (20^th anniversary special issue).

Hadwiger and Helly-type theorems for disjoint unit spheres (article, pdf, companion page)
O. Cheong, X. Goaoc, A. Holmsen and S. Petitjean.
Discrete and Computational Geometry 39(1-3): 194-212, 2008 (20^th anniversary special issue).

The number of lines tangent to arbitrary polytopes in R³ (article, pdf, research report, companion page)
H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na and S. Whiteside.
SIAM Journal on Computing 37(2): 522--551, 2007.

A note on maximally repeated sub-patterns of a point set (article, pdf, research report)
V. Cortier, X. Goaoc, M. Lee and H.-S. Na.
Discrete Mathematics 306(16): 1965--1968, 2006.

Tangents to spheres in R³ (article, pdf, research report, companion page)
C. Borcea, X. Goaoc, S. Lazard, and S. Petitjean.
Discrete and Computational Geometry 35(2): 287--300, 2006.

Geometric permutations of disjoint unit spheres (article, pdf, companion page)
O. Cheong, X. Goaoc and H.-S. Na.
Computational Geometry: Theory and Applications 30: 253--270, 2005.

The expected number of 3D visibility events is linear (article, pdf, research report, companion page)
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.

Refereed conferences

Admissible Linear Map Models of Linear Cameras
G. Batog, X. Goaoc and J. Ponce.
Proc. 23rd IEEE Conference in Computer Vision and Pattern Recognition (CVPR ), 2010.

Helly-type theorems for approximate covering (pdf, research report)
J. Demouth, O. Devillers, M. Glisse and X. Goaoc.
Proc. 24th ACM Symposium on Computational Geometry (SoCG ), pp. 120-128, 2008.

Empty-ellipse graphs (pdf, companion page, previous version as a research report)
O. Devillers, J. Erickson and X. Goaoc.
Proc. 19th Symposium on Discrete Algorithms (SODA), pp. 1249--1257, 2008.

Moving vertices to make drawings plane (pdf, arxiv)
X. Goaoc, J. Kratochvil, Y. Okamoto, C.-S. Shin, and A. Wolff.
Proc. 15th International Symposium on Graph Drawing (GD), LNCS 4875: 101--112, 2007.

Line transversals to disjoint balls (pdf)
C. Borcea, X. Goaoc and S. Petitjean.
Proc. 23rd ACM Symposium on Computational Geometry (SoCG ), pp 245--254, Gyeongju, 2007.

Hadwiger and Helly-type theorems for disjoint unit spheres (pdf, companion page)
O. Cheong, X. Goaoc and A. Holmsen.
Proc. 21th ACM Symposium on Computational Geometry (SoCG ), pp 10--15, Pisa, 2005.

A polynomial-time algorithm to design push plans for sensorless parts sorting (pdf)
M. de Berg, X. Goaoc and A.F. van der Stappen.
Proc. Robotics Science and Systems (RSS ), 2005.

The number of lines tangent to arbitrary polytopes in R³ (pdf, companion page)
H. Brönnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na and S. Whiteside.
Proc. 20th ACM Symposium on Computational Geometry (SoCG ), pp 46--55, 2004.

Disjoint unit spheres admit at most two line transversals (pdf, research report, companion page)
O. Cheong, X. Goaoc and H.-S. Na.

Proc. European Symposium on Algorithms (ESA ), LNCS 2832: 127--135, 2003.

Thesis

Structures de visibilité globales : taille, calcul et dégénérescences (pdf, companion page).
PhD thesis, May 2004.

Others

Lower Bounds for Pinning Lines by Balls (pdf)
O. Cheong, X. Goaoc and A. Holmsen.
EuroComb 2009.

Computing Direct Shadows Cast by Convex Polyhedra (pdf)
J. Demouth and X. Goaoc.
EuroCG 2009.

Topological Changes in the Apparent Contour of Convex Sets (pdf)
J. Demouth and X. Goaoc.
Manuscript, 2008.

Helly Numbers and Geometric Permutations
X. Goaoc.

Discrete Geometry seminar, Oberwolfach report 44/2008: 2541--2543.

There are arbitrary large minimal 2-pinning configurations (pdf)
X. Goaoc, H. Kim and J.-G. Lim.

First Annual Meeting of the Asian Association for Algorithms and Computation (AAAC), 2008.

On the visibility complex of disjoint balls in R³
X. Goaoc
Manuscript, 2006.

On tangents to quadric surfaces (arXiv)
C. Borcea, X. Goaoc, S. Lazard and S. Petitjean.
Manuscript, 2004.

On the worst-case complexity of the silhouette of a polytope (pdf)
H. Alt, M. Glisse and X. Goaoc.
Canadian Conference on Computational Geometry (CCCG ), 2003.

Last update: January 2010.