Sylvain Lazard's publications

• Non-linear Computational Geometry
• Visibility & Lines in space
• Misc.
• Curvature-Constrained Curves
• Linkages and Legged Robots
• Thesis

Non-linear Computational Geometry

• The Voronoi Diagram of Three Lines.
  Joint with H. Everett, D. Lazard and M. Safey El Din.
  Discrete and Computational Geometry, 42(1):94--130, 2009.
  (Special issue of invited papers from the 23th ACM Symposium on Computational Geometry, 2007.)
  INRIA Research Report No 6295, 38 pages, 2007.
• On The Topology of Planar Algebraic Curves. (full version)
  Joint with J. Cheng, L. Peñaranda, M. Pouget, F. Rouillier, and E. Tsigaridas.
  Proceedings of the 25th ACM Symposium on Computational Geometry, 2009.
• Univariate Algebraic Kernel and Application to Arrangements.
  Joint with L. Pearanda and E. Tsigaridas.
  Experimental Algorithms: 8th International Symposium SEA'09, LNCS 5526, pp. 209-220, 2009.
• The Voronoi diagram of three arbitrary lines in R³.
  Joint with H. Everett, C. Gillot, D. Lazard, and M. Pouget.
  Proceedings of the 25th European Workshop on Computational Geometry (EuroCG'09), 2009.
• Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm.
  Joint with L. Dupont, D. Lazard and S. Petitjean.
  Journal of Symbolic Computation,43(3):168--191 2008.
  INRIA Research Report no 5667, 2005, 36 pages.
• Near-Optimal Parameterization of the Intersection of Quadrics: II. A Classification of Pencils.
  Joint with L. Dupont, D. Lazard and S. Petitjean.
  Journal of Symbolic Computation, 43(3):192--215, 2008.
  INRIA Research Report no 5668, 2005, 37 pages.
  Erratum.
• Near-Optimal Parameterization of the Intersection of Quadrics: III. Parameterizing Singular Intersections.
  with L. Dupont, D. Lazard and S. Petitjean.
  Journal of Symbolic Computation, 43(3):216--232, 2008.
  INRIA Research Report no 5669, 2005, 34 pages.
• Intersecting Quadrics: An Efficient and Exact Implementation.
  Joint with Luis M. Peñaranda and S. Petitjean.
  Computational Geometry: Theory and Applications, 35(1-2):74--99, 2006.
  (Special issue of invited papers from the 20th ACM Symposium on Computational Geometry, 2004.)
  INRIA Research Report no 5670, 2005, 30 pages.
• Common Tangents to Spheres in R³.
  Joint with C. Borcea, X. Goaoc, and S. Petitjean.
  Discrete and Computational Geometry, 35(2):287-300, 2006.
  Rapport de Recherche INRIA No 5325, 2004, 16 pages.
• On tangents to quadric surfaces.
  Joint with C. Borcea, X. Goaoc, and S. Petitjean.
  Manuscript, 50 pages, 2004.
• Near-Optimal Parameterization of the Intersection of Quadrics.
  Joint with L. Dupont, D. Lazard and S. Petitjean.
  Proceedings of the 19th ACM Symposium on Computational Geometry, pp. 246-255, 2003.
• Towards the Robust Intersection of Implicit Quadrics.
  Joint with L. Dupont, D. Lazard and S. Petitjean.
  In J. Winkler and M. Niranjan, editors,Workshop on Uncertainty in Geometric Computations 2001, volume 704 of International Series in Engineering and Computer Science, chapter 5, pages 59-68. Kluwer Academic Publishers, August 2002.

Visibility & Lines in space

• On the Degree of Standard Geometric Predicates for Line Transversals in 3D.
  Joint with H. Everett, W. Lenhart and L. Zhang.
  Computational Geometry: Theory and Applications, 42(5):484--494, 2009.
  
• On the Complexity of Umbra and Penumbra.
  Joint with J. Demouth, O. Devillers, H. Everett, M. Glisse and R. Seidel.
  Computational Geometry: Theory and Applications, 42(8):758-771, 2009.
  (Special issue of invited papers from the 23rd European Workshop on Computational Geometry, 2007.)
  Proceedings of the 23th ACM Symposium on Computational Geometry, South-Korea, pp. 265--274, 2007.
• On the complexity of the sets of free lines and free line segments among balls in three dimensions.
  Joint with M. Glisse.
  Submitted to the 26th ACM Symposium on Computational Geometry, 2010.
• Predicates for 3D visibility.
  Joint with O. Devillers and M. Glisse.
  Proceedings of the 24th ACM Symposium on Computational Geometry, USA, pp. 174--181, 2008.
• On the size of the 3D visibility skeleton: Experimental results.
  Joint with L. Zhang, H. Everett, C. Weibel, and S. Whitesides.
  Proceedings of the 16th Annual European Symposium on Algorithms, vol. 5193 of LNCS, pp. 805--816. Springer, 2008.
• An Upper Bound on the Average Size of Silhouettes
  Joint with M. Glisse.
  Discrete and Computational Geometry, 40(2):241--257, 2008.
  INRIA Research Report No 6124, 19 pages, 2007.
• Towards an Implementation of the 3D Visibility Skeleton.
  Joint with L. Zhang, H. Everett, and S. Whitesides.
  Video of the 23rd Annual ACM Symposium on Computational Geometry, South-Korea, 2007.
• Lines Tangent to Four Triangles in Three-Dimensional Space.
  Joint with H. Brönnimann, O. Devillers, and F. Sottile.
  Discrete and Computational Geometry, 37(3):369-380, 2007.
  Proceedings of the 16th Canadian Conference on Computational Geometry, 2004.
  INRIA Research Report No 5693, 17 pages, 2005.
• Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra.
  Joint with H. Bronnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, H.-S. Na, and S. Whitesides.
  SIAM Journal on Computing, 37(2):522--551, 2007.
  Proceedings of the 20th ACM Symposium on Computational Geometry, 2004.
  INRIA Research Report No 5671, 28 pages, 2005.
• On the Expected Size of the 2D Visibility Complex.
  Joint with H. Everett, S. Petitjean, and L. Zhang.
  International Journal of Computational Geometry and Applications, 17(4):361 - 381, 2007.
  Proceedings of the 17th Canadian Conference on Computational Geometry, 2005.
  INRIA Research Report No 5822, 17 pages, 2006.
• Parabola Separation Queries and their Application to Stone Throwing.
  Joint with O. Cheong, H. Everett, H.-S. Kim, and R. Schott.
  International Journal of Computational Geometry and Applications,17(4):349 - 360, 2007.
• Common Tangents to Spheres in R³.
  Joint with C. Borcea, X. Goaoc, and S. Petitjean.
  Discrete and Computational Geometry, 35(2):287-300, 2006.
  Rapport de Recherche INRIA No 5325, 2004, 16 pages.
• Transversals to Line Segments in Three-Dimensional Space.
  Joint with H. Brönnimann, H. Everett, F. Sottile, and S. Whitesides.
  Discrete and Computational Geometry, 34(3):381--390, 2005.
  Proceedings of the 15th Canadian Conference on Computational Geometry, 2003.
  INRIA Research Report No 4864, 13 pages, 2003.
• On tangents to quadric surfaces.
  Joint with C. Borcea, X. Goaoc, and S. Petitjean.
  Manuscript, 50 pages, 2004.
• Orientation des pièces artistiques pour le procédé de Stratoconception.
  Joint with G. Lauvaux and C. Barlier.
  Proceedings of the 10th European Forum on Rapid Prototyping, 2004.
• The expected number of 3D visibility events is linear.
  Joint with O. Devillers, V. Dujmovic, H. Everett, X. Goaoc, H.-S. Na, and S. Petitjean.
  SIAM Journal on Computing, 32(6):1586-1620, 2003.
  INRIA Research Report No 4671, 42 pages, 2002.
• On the Number of Lines Tangent to Four Convex Polyhedra.
  Joint with H. Bronnimann, O. Devillers, V. Dujmovic, H. Everett, M. Glisse, X. Goaoc, H.-S. Na, S. Whitesides.
  Proceedings of the 14th Canadian Conference on Computational Geometry, 7 pages, 2002.
  

Misc.

• Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices.
  Joint with H. Everett, G. Liotta and S. Wismath.
  Accepted in Discrete and Computational Geometry, 2009.
  In 15th International Symposium on Graph Drawing, 2007, vol. 4875 of Lecture Notes in Computer Science, pp. 345--351, Springer, 2008.
• Homotopic Fréchet Distance Between Curves or, Walking Your Dog in the Woods in Polynomial Time.
  Joint with E. Wolf Chambers, É. Colin de Verdière, J. Erickson, F. Lazarus, and S. Thite.
  Proceedings of the 24th ACM Symposium on Computational Geometry, USA, pp. 101-- 109, 2008.
  Computational Geometry: Theory and Applications, 43:295-311, 2010.
  (Special issue of invited papers from the 24th ACM Symposium on Computational Geometry, 2008.)
• Farthest-Polygon Voronoi Diagrams
  Joint with O. Cheong, H. Everett, M. Glisse, J. Gudmundsson, S. Hornus, M. Lee and H.-S. Na.
  Proceedings of the 15th Annual European Symposium on Algorithms, vol. 4698 of LNCS, pp. 407--418. Springer, 2007.
• Drawing K_n in Three Dimensions with One Bend per Edge.
  Joint with O. Devillers, H. Everett, M. Pentcheva, and S. Wismath.
  Journal of Graph Algorithms and Applications, 10(2):287-295, 2006.
  Proceedings of the 13th International Symposium on Graph Drawing, 2005.
  INRIA Research Report No 5708, 10 pages, 2005.
  
• The Virtual Mesh: A Geometric Abstraction for Efficiently Computing Radiosity.
  Joint with L. Alonso, F. Cuny, S. Petitjean, J.-C. Paul and E. Wies.
  ACM Transactions on Graphics, 3(20):169-201, 2001.

Curvature-Constrained Curves

• A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles.
  Joint with J.-D. Boissonnat.
  International Journal of Computational Geometry and Applications, 13(3):189--229, 2003.
  Proceedings of the 12th ACM Symposium on Computational Geometry, 1996.
  INRIA Research Report No 2887, 45 pages, 1996.
• Curvature-constrained shortest path in a convex polygon.
  Joint with P.K. Agarwal, T. Biedl, S. Robbins, S. Suri, and S. Whitesides.
  SIAM Journal on Computing 31(6):1814--1851, 2002.
  Proceedings of the 14th ACM Symposium on Computational Geometry, 1998.
  INRIA Research Report No 4063, 59 pages, 2000.
• An algorithm for computing a convex and simple path of bounded curvature in a simple polygon.
  Joint with J-D. Boissonnat, S.K. Ghosh and T. Kavitha.
  Algorithmica, 34:109-156, 2002.
• Interpolation problem with curvature constraints.
  Joint with H. Deddi and H. Everett.
  Curve and Surface Fitting: Saint-Malo 1999, A. Cohen, C. Rabut, and L. L. Schumaker (eds.), Vanderbilt University Press, Nashville TN, 2000, pages 191--200.
  INRIA Research Report No 4064, 20 pages, 2000.

• Convex hulls of bounded curvature.
  Joint with J.-D. Boissonnat.
  Proceedings of the 8th Canadian Conference on Computational Geometry, Ottawa, 1996, pp. 14-19.

Linkages and Legged Robots

• Convexifying Monotone Polygons.
  Joint with T.Biedl, E. Demaine, S. Robbins, and M. Soss.
  Proceedings of the 10th Annual International Symposium on Algorithms and Computation
  Lecture Notes in Computer Science, Chennai, India, December 16-18, 1999, pp. 415-424.
• Locked and Unlocked Polygonal Chains in Three Dimensions.
  Joint with T. Biedl, E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G.Toussaint, and S. Whitesides.
  Discrete and Computational Geometry, 26(3):269-282, 2001.
  Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
• Convexifying star shaped polygons.
  Joint with H. Everett, S. Robbins, H. Schroder, and S. Whitesides.
  Proceedings of the 10th Canadian Conference on Computational Geometry, Montréal, Québec, Canada, August 10-12, 1998.
• A Note on Reconfiguring Tree Linkages: Trees can Lock
  Joint with T. Biedl, E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides.
  Discrete Applied Mathematics, 117 (2002) 293--297.
  Proceedings of the 10th Canadian Conference on Computational Geometry, 1998.
• Motion planning of legged robots.
  Joint with J.-D. Boissonnat and O. Devillers.
  SIAM Journal on Computing, 30(1):218-246, 2001.
  Proceedings of the First 1st Workshop on the Algorithmic Foundations of Robotics, A. K. Peters, Boston, MA, 1994.
  INRIA Research Report No 3214, 60 pages, 1997.

• From spider robots to half disk robots.
  Joint with J.-D. Boissonnat and O. Devillers.
  Proceedings of the 11th IEEE International Conference on Robotics and Automation, San Diego, CA, 1994, pp. 953-958.

Thesis

• Problèmes de géométrie algorithmique sur les droites et les quadriques en trois dimensions. (English version)
  Thèse d'habilitation à diriger des recherches de l'université Nancy 2, spécialité informatique. Soutenue le 24 septembre 2007.
• Planification de trajectoires de robots mobiles non-holonomes et de robots à pattes.
  Thèse de doctorat en science de l'Université Paris 6, spécialité Informatique.
  Soutenue le 9 mai 1996, à Paris.