Geometrica Home Publications of Olivier Devillers
BACK TO INDEX

Publications of Olivier Devillers
Books and proceedings
  1. Olivier Devillers, editor. Proceedings of the 30th Annual Symposium on Computational Geometry, June 8-11 2014. ACM. [WWW]


  2. J-D. Boissonnat and O. Devillers, editors. Journées de Géométrie Algorithmique, 1990. INRIA.


Thesis
  1. Olivier Devillers. Randomisation, sphères et déplacements de robots. Habilitation à diriger des recherches, Université de Nice Sophia Antipolis, France, 1993. [WWW]


Articles in journal, book chapters
  1. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry, 5:56-85, 2014. [WWW]


  2. Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman, and Pat Morin. Oja centers and centers of gravity. Computational Geometry: Theory and Applications, 46:140-147, 2013. [WWW] [doi:10.1016/j.comgeo.2012.04.004]


  3. Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, and Matthias Reitzner. The monotonicity of $f$-vectors of random polytopes. Electronic Communications in Probability, 18(23):1-8, 2013. [WWW] [doi:10.1214/ECP.v18-2469]


  4. Pedro Machado Manhães de Castro and Olivier Devillers. Practical Distribution-Sensitive Point Location in Triangulations. Computer Aided Geometric Design, 30:431-450, 2013. [WWW] [doi:10.1016/j.cagd.2013.02.004]


  5. Nina Amenta, Dominique Attali, and Olivier Devillers. A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron. Discrete & Computational Geometry, 48:19-38, 2012. [WWW] [doi:10.1007/s00454-012-9415-7]


  6. Luca Castelli Aleardi, Olivier Devillers, and Abdelkrim Mebarki. Catalog Based Representation of 2D triangulations. Internat. J. Comput. Geom. Appl., 21:393-402, 2011. [WWW] [doi:10.1142/S021819591100372X]


  7. Olivier Devillers. Delaunay Triangulation of Imprecise Points: Preprocess and Actually Get a Fast Query Time. Journal of Computational Geometry, 2:30-45, 2011. [WWW]


  8. Olivier Devillers. Vertex Removal in Two Dimensional Delaunay Triangulation: Speed-up by Low Degrees Optimization. Computational Geometry: Theory and Applications, 44:169-177, 2011. [WWW] [doi:10.1016/j.comgeo.2010.10.001]


  9. Olivier Devillers and Monique Teillaud. Perturbations for Delaunay and weighted Delaunay 3D Triangulations. Computational Geometry: Theory and Applications, 44:160-168, 2011. [WWW] [doi:10.1016/j.comgeo.2010.09.010]


  10. Pedro Machado Manhães de Castro and Olivier Devillers. On the Size of Some Trees Embedded in $\mathbb{R}^d$. Operations Research Letters, 39:44-48, 2011. [WWW] [doi:10.1016/j.orl.2010.10.005]


  11. Christophe Delage and Olivier Devillers. Spatial Sorting. In CGAL User and Reference Manual. CGAL Editorial Board, 3.9 edition, 2011. [WWW]


  12. Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, and Sven Schönherr. Geometric Object Generators. In CGAL User and Reference Manual. CGAL Editorial Board, 3.9 edition, 2011. [WWW]


  13. Jane Tournois, Pierre Alliez, and Olivier Devillers. 2D Centroidal Voronoi Tessellations with Constraints. Numer. Math. Theor. Meth. Appl., 3:212-222, 2010. Note: Special issue for Centroidal Voronoi Tessellations. [WWW] [doi:10.4208/nmtma.2010.32s.6]


  14. Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, and Raimund Seidel. On the complexity of umbra and penumbra. Comput. Geom. Theory Appl., 42:758-771, 2009. [WWW] [doi:10.1016/j.comgeo.2008.04.007]


  15. Julien Demouth, Olivier Devillers, Marc Glisse, and Xavier Goaoc. Helly-type theorems for approximate covering. Discrete & Computational Geometry, 42:379-398, 2009. [WWW] [doi:10.1007/s00454-009-9167-1]


  16. Pedro Machado Manhães de Castro, Jane Tournois, Pierre Alliez, and Olivier Devillers. Filtering relocations on a Delaunay triangulation. Computer Graphics Forum, 28:1465-1474, 2009. Note: Special issue 6th Annu. Sympos. Geometry Processing. [WWW]


  17. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Succinct representations of planar maps. Theoretical Computer Science, 408:174-187, 2008. [WWW]


  18. H. Brönnimann, O. Devillers, Vida Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. SIAM Journal on Computing, 37:522-551, 2007. [WWW]


  19. Hervé Brönnimann, Olivier Devillers, Sylvain Lazard, and Frank Sottile. Lines tangent to four triangles in three-dimensional space. Discrete and Computational Geometry, 37:369-380, 2007. [WWW]


  20. Olivier Devillers, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, and Steve Wismath. Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint. Internat. J. Comput. Geom. Appl., 17:297-304, 2007. [WWW] [doi:10.1142/S0218195907002343]


  21. Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, and Stephen Wismath. Drawing $K_n$ in Three Dimensions with One Bend per Edge. Journal of Graph Algorithms and Applications, 10:287-295, 2006. [WWW]


  22. Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical Models, 67, 2005. [WWW] [doi:10.1016/j.gmod.2004.06.007]


  23. Olivier Devillers and Philippe Guigue. Inner and Outer Rounding of Boolean Operations on Lattice Polygonal Regions. Computational Geometry: Theory and Applications, 33:3-17, 2005. [WWW]


  24. Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun. Anisotropic Polygonal Remeshing. ACM Transactions on Graphics, 22:485-493, 2003. Note: SIGGRAPH '2003 Conference Proceedings. [WWW]


  25. Olivier Devillers. On the Number of Cylindrical Shells. Discrete and Computational Geometry, 30:453-458, 2003. [WWW]


  26. Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, and Sylvain Petitjean. The expected number of 3D visibility events is linear. SIAM Journal on Computing, 32:1586-1620, 2003. [WWW]


  27. Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, and Vera Sacristán. Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction. Internat. J. Comput. Geom. Appl., 13:391-398, 2003. [WWW] [doi:10.1142/S0218195903001244]


  28. Olivier Devillers, Ferran Hurtado, Gyula Károlyi, and Carlos Seara. Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position. Computational Geometry: Theory and Applications, 26:193-208, 2003. [WWW]


  29. Olivier Devillers, Bernard Mourrain, Franco P. Preparata, and Philippe Trebuchet. Circular Cylinders by Four or Five Points in Space. Discrete and Computational Geometry, 29:83-104, 2003. [WWW]


  30. Olivier Devillers and Franco P. Preparata. Culling a Set of Points for Roundness or Cylindricity Evaluations. Internat. J. Comput. Geom. Appl., 13:231-240, 2003. [WWW] [doi:10.1142/S021819590300113X]


  31. Philippe Guigue and Olivier Devillers. Fast and Robust Triangle-Triangle Overlap Test Using Orientation Predicates. Journal of graphics tools, 8(1):39-52, 2003. [WWW] [doi:10.1080/10867651.2003.10487580]


  32. Jean-Daniel Boissonnat, Olivier Devillers, Sylvain Pion, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. Computational Geometry: Theory and Applications, 22:5-19, 2002. [WWW] [doi:10.1016/S0925-7721(01)00054-2]


  33. Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristán, and Monique Teillaud. Splitting a Delaunay Triangulation in Linear Time. Algorithmica, 34:39-46, 2002. [WWW]


  34. Olivier Devillers. On Deletion in Delaunay Triangulation. Internat. J. Comput. Geom. Appl., 12:193-205, 2002. [WWW] [doi:10.1142/S0218195902000815]


  35. Olivier Devillers. The Delaunay hierarchy. Internat. J. Found. Comput. Sci., 13:163-180, 2002. [WWW] [doi:10.1142/S0129054102001035]


  36. Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Computational Geometry: Theory and Applications, 22:119-142, 2002. [WWW]


  37. Olivier Devillers and Pierre-Marie Gandoin. Rounding Voronoi Diagram. Theoret. Comput. Sci., 283/1:203-221, 2002. [WWW] [doi:10.1016/S0304-3975(01)00076-7]


  38. Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181-199, 2002. [WWW] [doi:10.1142/S0129054102001047]


  39. Olivier Devillers and Pedro Ramos. Computing Roundness is Easy if the Set is Almost Round. Internat. J. Comput. Geom. Appl., 12:229-248, 2002. [WWW] [doi:10.1142/S0218195902000840]


  40. Pierre-Marie Gandoin and Olivier Devillers. Progressive Lossless Compression of Arbitrary Simplicial Complexes. ACM Transactions on Graphics, 21:372-379, 2002. Note: SIGGRAPH '2002 Conference Proceedings. [WWW]


  41. Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, and Mariette Yvinec. Circular Separability of Polygons. Algorithmica, 30:67-82, 2001. [WWW]


  42. Olivier Devillers and Philippe Guigue. The shuffling buffer. Internat. J. Comput. Geom. Appl., 11:555-572, 2001. [WWW] [doi:10.1142/S021819590100064X]


  43. Pierre Alliez, Olivier Devillers, and Jack Snoeyink. Removing Degeneracies by Perturbing the Problem or the World. Reliable Computing, 6:61-79, 2000. Note: Special Issue on Computational Geometry. [WWW]


  44. Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jorge Urrutia, and Mariette Yvinec. Computing Largest Circles Separating Two Sets of Segments. Internat. J. Comput. Geom. Appl., 10:41-54, 2000. [WWW] [doi:10.1142/S0218195900000036]


  45. Jean-Daniel Boissonnat, Olivier Devillers, and Sylvain Lazard. Motion Planning of Legged Robots. SIAM Journal on Computing, 30:218-246, 2000. [WWW]


  46. Jean-Daniel Boissonnat, Jurek Czyzowicz, Olivier Devillers, Jean-Marc Robert, and Mariette Yvinec. Convex Tours of Bounded Curvature. Computational Geometry: Theory and Applications, 13:149-160, 1999. [WWW]


  47. Olivier Devillers and Matthew Katz. Optimal Line Bipartitions of Point Sets. Internat. J. Comput. Geom. Appl., 9:39-51, 1999. [WWW] [doi:10.1142/S0218195999000042]


  48. Olivier Devillers and Asish Mukhopadhyay. Finding an ordinary conic and an ordinary hyperplane. Nordic Journal of Computing, 6:462-468, 1999. [WWW]


  49. Olivier Devillers and Franco P. Preparata. Further Results on Arithmetic Filters for Geometric Predicates. Computational Geometry: Theory and Applications, 13:141-148, 1999. [WWW]


  50. O. Devillers and M. Golin. Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems. Internat. J. Comput. Geom. Appl., 8:321-342, 1998. [WWW] [doi:10.1142/S0218195998000163]


  51. Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Computational Geometry: Theory and Applications, 11:187-208, 1998. [WWW]


  52. O. Devillers and F. P. Preparata. A probabilistic analysis of the power of arithmetic filters. Discrete and Computational Geometry, 20:523-547, 1998. [WWW]


  53. Mark de Berg, Otfried Cheong, Olivier Devillers, Marc van Kreveld, and Monique Teillaud. Computing the Maximum Overlap of Two Convex Polygons Under Translations. Theory of Computing Systems, 31:613-628, 1998. [WWW]


  54. F. Avnaim, J-D. Boissonnat, O. Devillers, F. P. Preparata, and M. Yvinec. Evaluating signs of determinants using single-precision arithmetic. Algorithmica, 17:111-132, 1997. [WWW]


  55. M. de Berg, O. Devillers, K. Dobrindt, and O. Schwarzkopf. Computing a single cell in the union of two simple polygons. Inform. Process. Lett., 63:215-219, 1997. [WWW]


  56. J-D. Boissonnat, A. Cérézo, O. Devillers, J. Duquesne, and M. Yvinec. An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension $d$. Computational Geometry: Theory and Applications, 6:123-130, 1996. [WWW]


  57. J.-D. Boissonnat, A. Cérézo, O. Devillers, and M. Teillaud. Output-sensitive construction of the Delaunay triangulation of points lying in two planes. Internat. J. Comput. Geom. Appl., 6(1):1-14, 1996. [WWW] [doi:10.1142/S0218195996000022]


  58. O. Devillers. An introduction to randomization in computational geometry. Theoret. Comput. Sci., 157:35-52, 1996. [WWW]


  59. O. Devillers and A. Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. Internat. J. Comput. Geom. Appl., 6:487-506, 1996. [WWW] [doi:10.1142/S0218195996000307]


  60. O. Devillers, M. Golin, K. Kedem, and S. Schirra. Queries on Voronoi Diagrams of Moving Points. Computational Geometry: Theory and Applications, 6:315-327, 1996. [WWW]


  61. J.-D. Boissonnat, O. Devillers, L. Donati, and F. P. Preparata. Motion planning of legged robots: the spider robot problem. Internat. J. Comput. Geom. Appl., 5(1& 2):3-20, 1995. [WWW] [doi:10.1142/S0218195995000027]


  62. O. Devillers and M. Golin. Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas. Inform. Process. Lett., 56(3):157-164, 1995. [WWW]


  63. J-D. Boissonnat, O. Devillers, J. Duquesne, and M. Yvinec. Computing Connolly Surfaces. J. Mol. Graphics, 12:61-62, 1994. [WWW] [doi:10.1016/0263-7855(94)80033-2]


  64. J.-D. Boissonnat, O. Devillers, and M. Teillaud. A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica, 9:329-356, 1993. [WWW] Keyword(s): randomized algorithms, higher order Voronoi diagrams, dynamic algorithms.


  65. Olivier Devillers. Simultaneous containment of several polygons: analysis of the contact configurations. Internat. J. Comput. Geom. Appl., 3(4):429-442, 1993. [WWW] [doi:10.1142/S0218195993000270]


  66. J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete and Computational Geometry, 8:51-71, 1992. [WWW] Keyword(s): randomized algorithms, Delaunay triangulation, semi-dynamic algorithms, arrangement of line-segments.


  67. O. Devillers. Randomization yields simple $O(n \log^{*} n)$ algorithms for difficult $\Omega(n)$ problems. Internat. J. Comput. Geom. Appl., 2(1):97-111, 1992. [WWW] [doi:10.1142/S021819599200007X] Keyword(s): randomized algorithms, Delaunay triangulation, skeleton, medial axis, minimum spanning tree, simple polygon.


  68. O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Computational Geometry: Theory and Applications, 2(2):55-80, 1992. [WWW] Keyword(s): randomized algorithms, Delaunay triangulation, dynamizing data structures.


  69. O. Devillers, M. Teillaud, and M. Yvinec. Dynamic location in an arrangement of line segments in the plane. Algorithms Review, 2(3):89-103, 1992. [WWW] Keyword(s): randomized algorithms, arrangement of line-segments, dynamizing data structures.


  70. J.-D. Boissonnat, O. Devillers, and F. P. Preparata. Computing the union of $3$-colored triangles. Internat. J. Comput. Geom. Appl., 1(2):187-196, 1991. [WWW] [doi:10.1142/S021819599100013X] Keyword(s): convex hull, motion plannig, legged robot.


Conference articles
  1. Dominique Attali, Olivier Devillers, Macr Glisse, and Sylvain Lazard. Recognizing shrinkable complexes is NP-complete. In Proc. 22nd European Symposium on Algorithms, volume 8737 of LNCS, pages 74-86, 2014. [WWW]


  2. Nicolas Broutin, Olivier Devillers, and Ross Hemsley. Efficiently Navigating a Random Delaunay Triangulation. In Proc. of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm, 2014. [WWW]


  3. Nicolas Broutin, Olivier Devillers, and Ross Hemsley. The Maximum Degree of a Random Delaunay Triangulation in a Smooth Convex. In Posters of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm, 2014. [WWW]


  4. Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. Crossing-free straight-line drawing of graphs on the flat torus. In Workshop on Geometric Structures with Symmetry and Periodicity, 2014. Note: Computational Geometry Week, Kyoto. [WWW]


  5. Olivier Devillers, Philippe Duchon, and Rémy Thomasse. A generator of random convex polygons in a disc. In Posters of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm, 2014. [WWW]


  6. Olivier Devillers, Marc Glisse, and Rémy Thomasse. A chaotic random convex hull. In Posters of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm, 2014. [WWW]


  7. Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. Homological reconstruction and simplification in $I\!\!R^3$. In Proc. of the 29th Annual Symposium on Computational Geometry, pages 117-125, 2013. [WWW] [doi:10.1145/2462356.2462373]


  8. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. In Proc. of the 29th Annual Symposium on Computational Geometry, pages 67-76, 2013. [WWW] [doi:10.1145/2462356.2462365]


  9. Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers, and Jonathan Shewchuk. Vertex Deletion for 3D Delaunay Triangulations. In Proc. 21th European Symposium on Algorithms, volume 8125 of LNCS, pages 253-264, 2013. [WWW]


  10. Olivier Devillers, Marc Glisse, and Xavier Goaoc. Complexity analysis of random geometric structures made simpler. In Proc. of the 29th Annual Symposium on Computational Geometry, pages 167-175, 2013. [WWW] [doi:10.1145/2462356.2462362]


  11. Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. In Proc. 20th International Symposium on Graph Drawing, volume 7704 of LNCS, pages 376-387, 2012. [WWW]


  12. Luca Castelli Aleardi, Olivier Devillers, and Jarek Rossignac. ESQ: Editable SQuad representation for triangle meshes. In XXV SIBGRAPI - Conference on Graphics, Patterns and Images, pages 110-117, 2012. [WWW] [doi:10.1109/SIBGRAPI.2012.24]


  13. Olivier Devillers. Delaunay Triangulations, theory vs practice. In Abstracts 28th European Workshop on Computational Geometry, pages 1-4, 2012. Note: Invited talk. [WWW]


  14. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay triangulations and Voronoi diagrams made practical. In Abstracts XIV Spanish Meeting on Computational Geometry, pages 113-116, 2011. [WWW]


  15. Luca Castelli Aleardi and Olivier Devillers. Explicit array-based compact data structures for planar and surface meshes. In Abstracts XIV Spanish Meeting on Computational Geometry, pages 237-240, 2011. [WWW]


  16. Luca Castelli Aleardi and Olivier Devillers. Explicit array-based compact data structures for triangulations. In Proc. 22th Annu. Internat. Sympos. Algorithms Comput., volume 7074 of LNCS, pages 312-322, 2011. [WWW]


  17. Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. In Abstracts XIV Spanish Meeting on Computational Geometry, pages 105-108, 2011. [WWW]


  18. Pedro Machado Manhães de Castro and Olivier Devillers. A Pedagogic JavaScript Program for Point Location Strategies. In Video of 27th Annual Symposium on Computational Geometry, pages 295-296, 2011. [WWW]


  19. Pedro Machado Manhães de Castro and Olivier Devillers. Simple and Efficient Distribution-Sensitive Point Location, in Triangulations. In Workshop on Algorithm Engineering and Experiments, pages 127-138, 2011. [WWW]


  20. Dan Chen, Olivier Devillers, John Iacono, Stefan Langerman, and Pat Morin. Oja Medians and Centers of Gravity. In Proc. 22th Canad. Conf. Comput. Geom., 2010. [WWW]


  21. Oswin Aichholzer, Franz Aurenhammer, Olivier Devillers, Thomas Hackl, Monique Teillaud, and Birgit Vogtenhuber. Lower and upper bounds on the number of empty cylinders and ellipsoids. In Abstracts 25th. European Workshop on Computational Geometry, pages 139-142, 2009. [WWW]


  22. Jean-Daniel Boissonnat, Olivier Devillers, and Samuel Hornus. Incremental construction of the Delaunay graph in medium dimension. In Proc. 25th Annual Symposium on Computational Geometry, pages 208-216, 2009. [WWW]


  23. Pedro Machado Manhães de Castro and Olivier Devillers. Fast Delaunay Triangulation for Converging Point Relocation Sequences. In Abstracts 25th. European Workshop on Computational Geometry, pages 231-234, 2009. [WWW]


  24. Julien Demouth, Olivier Devillers, Marc Glisse, and Xavier Goaoc. Helly-type theorems for approximate covering. In Proceedings of the 24th Annual Symposium Computational Geometry, pages 120-128, 2008. [WWW] [doi:10.1145/1377676.1377696]


  25. Olivier Devillers, Jeff Erickson, and Xavier Goaoc. Empty-ellipse graphs. In Proc. 19th ACM-SIAM Sympos. Discrete Algorithms, pages 1249-1256, 2008. [WWW]


  26. Olivier Devillers, Marc Glisse, and Sylvain Lazard. Predicates for Line Transversals to Lines and Line Segments in Three-dimensional Space. In Proc. 24th Annual Symposium on Computational Geometry, pages 174-181, 2008. [WWW]


  27. Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. In Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pages 1106-1113, 2007. [WWW]


  28. Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, and Raimund Seidel. Between umbra and penumbra. In Proc. 23th Annual Symposium on Computational Geometry, pages 265-274, 2007. [WWW] [doi:10.1145/1247069.1247117]


  29. Jane Tournois, Pierre Alliez, and Olivier Devillers. Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation. In Meshing Roundtable conference proceedings, pages 83-101, 2007.


  30. Luca Castelli Aleardi, Olivier Devillers, and Abdelkrim Mebarki. 2D Triangulation Representation Using Stable Catalogs. In Proc. 18th Canad. Conf. Comput. Geom., pages 71-74, 2006. [WWW]


  31. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Optimal Succinct Representations of Planar Maps. In Proc. 22th Annual Symposium on Computational Geometry, pages 309-318, 2006. [WWW]


  32. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Dynamic updates of succinct triangulations. In Proc. 17th Canad. Conf. Comput. Geom., pages 135-138, 2005. [WWW]


  33. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Succinct representation of triangulations with a boundary. In Proc. 9th Workshop on Algorithms and Data Structures, volume 3608 of Lecture Notes in Computer Science, pages 134-135, 2005. Springer-Verlag. [WWW]


  34. Olivier Devillers, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, and Steve Wismath. Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint. In Proc. 17th Canad. Conf. Comput. Geom., pages 302-305, 2005. [WWW]


  35. Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, and Stephen Wismath. Drawing $K_n$ in Three Dimensions with One Bend per Edge. In Proc. 13th Int. Symp. on Graph Drawing, 2005. [WWW]


  36. Pau Estalella, Ignacio Martin, George Drettakis, Dani Tost, Olivier Devillers, and Frédéric Cazals. Accurate Interactive Specular Reflections on Curved Objects. In Vision, Modeling, and Visualization 2005, 2005.


  37. Abdelkrim Mebarki, Pierre Alliez, and Olivier Devillers. Farthest Point Seeding for Efficient Placement of Streamlines. In Proc. of IEEE Visualization, 2005.


  38. H. Brönnimann, O. Devillers, Vida Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D. In Proc. 20th Annual Symposium on Computational Geometry, pages 46-59, 2004. [WWW]


  39. Hervé Brönnimann, Olivier Devillers, Sylvain Lazard, and Frank Sottile. On the number of line tangents to four triangles in three-dimensional space. In Proc. 10th Canad. Conf. Comput. Geom., 2004.


  40. Olivier Devillers and Philippe Guigue. Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions. In Proc. 20th Annual Symposium on Computational Geometry, pages 429-437, 2004.


  41. Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. Isotropic Surface Remeshing. In International Conference on Shape Modeling and applications, pages 49-58, 2003. [WWW]


  42. Pierre Alliez, Olivier Devillers, Martin Isenburg, and Sebastien Valette. Compression de maillages, un état de l'art. In CORESA, 2003.


  43. Olivier Devillers and Sylvain Pion. Efficient Exact Geometric Predicates for Delaunay Triangulations. In Proc. 5th Workshop Algorithm Eng. Exper., pages 37-44, 2003. [WWW]


  44. Olivier Devillers and Monique Teillaud. Perturbations and Vertex Removal in a 3D Delaunay Triangulation. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pages 313-319, 2003. [WWW]


  45. Mario Trentini, Olivier Devillers, and Pierre-Marie Gandoin. Transmission progressive de modèles triangulés sur le réseau. In CORESA, 2003.


  46. H. Brönnimann, O. Devillers, Vida Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. On the Number of Lines Tangent to Four Convex Polyhedra. In Proc. 8th Canad. Conf. Comput. Geom., pages 113-117, 2002.


  47. Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristán, and Monique Teillaud. Splitting a Delaunay Triangulation in Linear Time. In Proc. 9th. European Symposiun on Algorithms, volume 2161 of Lecture Notes in Computer Science, pages 312-320, 2001. Springer-Verlag.


  48. Olivier Devillers and Philippe Guigue. The shuffling buffer. In Proc. 13th Canad. Conf. Comput. Geom., 2001. [WWW]


  49. Olivier Devillers, Ferran Hurtado, Mercè Mora, and Carlos Seara. Separating Several Point Sets in the Plane. In Proc. 13th Canad. Conf. Comput. Geom., 2001. [WWW]


  50. Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. In Proc. 17th Annual Symposium on Computational Geometry, pages 106-114, 2001. [WWW]


  51. Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. In Proc. 16th Annual Symposium on Computational Geometry, pages 11-18, 2000.


  52. Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Exact predicates for circle arcs arrangements. In Proc. 16th Annual Symposium on Computational Geometry, pages 139-147, 2000.


  53. Olivier Devillers and Pierre-Marie Gandoin. Geometric Compression for Interactive Transmission. In Proc. of IEEE Visualization 2000, pages 319-326, 2000.


  54. Olivier Devillers and Franco P. Preparata. Evaluating the cylindricity of a nominally cylindrical point set. In Proc. 11th ACM-SIAM Sympos. Discrete Algorithms, pages 518-527, 2000. [WWW]


  55. Jean-Daniel Boissonnat, Frédéric Cazals, Tran Kai Frank Da, Olivier Devillers, Sylvain Pion, François Rebufat, Monique Teillaud, and Mariette Yvinec. Programming with CGAL: The Example of Triangulations. In Proc the 15th Annual Symposium on Computational Geometry, pages 421-423, 1999. [WWW]


  56. Olivier Devillers. On Deletion in Delaunay Triangulation. In Proc. 15th Annual Symposium on Computational Geometry, pages 181-188, 1999. [WWW]


  57. Olivier Devillers and Pierre-Marie Gandoin. Rounding Voronoi Diagram. In Proc. 8th Discrete Geometry and Computational Imagery conference (DGCI99), volume 1568 of Lecture Notes in Computer Science, pages 375-387, 1999. Springer-Verlag.


  58. P. Alliez, O. Devillers, and J. Snoeyink. Removing Degeneracies by Perturbing the Problem or the World. In Proc. 10th Canad. Conf. Comput. Geom., 1998. [WWW]


  59. O. Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annual Symposium on Computational Geometry, pages 106-115, 1998. [WWW]


  60. O. Devillers, G. Liotta, F. P. Preparata, and R. Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. In Proc. 5nd Workshop Algorithms Data Struct., volume 1272 of Lecture Notes in Computer Science, pages 186-199, 1997. Springer-Verlag. [WWW]


  61. J-D. Boissonnat, J. Czyzowicz, O. Devillers, J. Urrutia, and M. Yvinec. Computing Largest Circles Separating Two Sets of Segments. In Proc. 8th Canad. Conf. Comput. Geom., pages 173-178, 1996.


  62. O. Devillers. Computational geometry and discrete computations. In Proc. 6th Discrete Geometry for Computer Imagery conf., volume 1176 of Lecture Notes in Computer Science, pages 317-324, 1996. Springer-Verlag. Note: (invited paper). [WWW]


  63. O. Devillers and M. Katz. Optimal Line Bipartitions of Point Sets. In Proc. 7th Annu. Internat. Sympos. Algorithms Comput. (ISAAC 96), volume 1178 of Lecture Notes in Computer Science, pages 45-54, 1996. Springer-Verlag.


  64. Mark de Berg, Otfried Cheong, Olivier Devillers, Marc van Kreveld, and Monique Teillaud. Computing the Maximum Overlap of Two Convex Polygons Under Translations. In Proc. 7th Annu. Internat. Sympos. Algorithms Comput. (ISAAC 96), volume 1178 of Lecture Notes in Computer Science, pages 126-135, 1996. Springer-Verlag.


  65. F. Avnaim, J.-D. Boissonnat, O. Devillers, F. P. Preparata, and M. Yvinec. Evaluation of a new method to compute signs of determinants. In Proc. of the 11th Annu. Symposium on Computational Geometry, pages C16-C17, 1995. [WWW]


  66. J-D. Boissonnat, J. Czyzowicz, O. Devillers, and M. Yvinec. Circular Separability of Polygons. In Proc. 6th ACM-SIAM Sympos. Discrete Algorithms, 1995.


  67. Pascal Desnoguès and Olivier Devillers. A Locally Optimal Triangulation of the Hyperbolic Paraboloid. In Proc. 7th Canad. Conf. Comput. Geom., pages 49-54, 1995. [WWW]


  68. J-D. Boissonnat, J. Czyzowicz, O. Devillers, J-M. Robert, and M. Yvinec. Convex Tours of Bounded Curvature. In Proc. 2nd. European Symposiun on Algorithms, volume 855 of Lecture Notes in Computer Science, pages 254-265, 1994. Springer-Verlag.


  69. Jean-Daniel Boissonnat, Olivier Devillers, and Sylvain Lazard. From Spiders Robots to Half Disks Robots. In Proc. 11th IEEE Internat. Conf. Robot. Autom., pages 953-958, 1994.


  70. Jean-Daniel Boissonnat, Olivier Devillers, and Sylvain Lazard. Motion Planning of Legged Robots. In The First Workshop on the Algorithmic Foundations of Robotics, 1994. A. K. Peters, Boston, MA.


  71. O. Devillers. An introduction to randomization in computational geometry. In Workshop on Algorithmic Complexity of Algebraic and Geometric Models, 1994. [WWW]


  72. O. Devillers and M. Golin. Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. In Proc. 6th Canad. Conf. Comput. Geom., pages 153-158, 1994. Keyword(s): Algorithms, Convex Hulls, Circles, Parabolas, Lower Envelopes.


  73. O. Devillers, M. Golin, K. Kedem, and S. Schirra. Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points. In Proc. 6th Canad. Conf. Comput. Geom., pages 122-127, 1994. Keyword(s): Algorithms, Convex Hulls, Circles, Parabolas, Lower Envelopes.


  74. J-D. Boissonnat, O. Devillers, J. Duquesne, and M. Yvinec. Computing the whole set of Connolly Surfaces. In 12 th Annual Conference of the Molecular Graphics Society, 1993.


  75. O. Devillers and A. Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. In Proc. 3rd Workshop Algorithms Data Struct., volume 709 of Lecture Notes in Computer Science, pages 277-288, 1993. Springer-Verlag.


  76. O. Devillers and M. Golin. Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems. In Proc. 1st. European Symposiun on Algorithms, volume 294 of Lecture Notes in Computer Science, pages 133-144, 1993. Springer-Verlag.


  77. J-D. Boissonnat, A. Cérézo, O. Devillers, J. Duquesne, and M. Yvinec. An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension $d$. In Proc. 4th Canad. Conf. Comput. Geom., pages 269-273, 1992.


  78. J.-D. Boissonnat, O. Devillers, L. Donati, and F. P. Preparata. Motion planning for a spider robot. In Proc. 9th IEEE Internat. Conf. Robotics and Automat., pages 2321-2326, 1992. Keyword(s): motion plannig, legged robot.


  79. J.-D. Boissonnat, O. Devillers, L. Donati, and F. P. Preparata. Stable placements of spider robots. In Proc. 8th Annual Symposium on Computational Geometry, pages 242-250, 1992. Keyword(s): motion plannig, legged robot.


  80. J-D. Boissonnat, O. Devillers, and J. Duquesne. Computing Connolly Surfaces. In IFIP Conference on Algorithms and efficient computation, 1992.


  81. J-D. Boissonnat, O. Devillers, and F. P. Preparata. Computing the Union of 3-Colored Triangles. In Proc. 15th IFIP Conf., volume 180 of Lecture Notes in Control and Information Science, pages 85-93, 1992. Springer-Verlag.


  82. O. Devillers, S. Meiser, and M. Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. In Proc. 4th Canad. Conf. Comput. Geom., pages 263-268, 1992.


  83. O. Devillers and N. Mouawad. Guarding Vertices versus Guarding Edges in a Simple Polygon. In Proc. 4th Canad. Conf. Comput. Geom., pages 99-102, 1992.


  84. J.-D. Boissonnat, A. Cérézo, O. Devillers, and M. Teillaud. Output-sensitive construction of the $3$-d Delaunay triangulation of constrained sets of points. In Proc. 3rd Canad. Conf. Comput. Geom., pages 110-113, 1991. Keyword(s): Delaunay triangulation, Voronoi diagrams, output-sensitive algorithms, shape reconstructions, shelling, tomography.


  85. J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. On-line geometric algorithms with good expected behaviours. In Proc. 13th World Congress on Computation and Applied Math., pages 137-139, 1991.


  86. O. Devillers. Simple randomized $O(n \log^{*} n)$ algorithms. In Proc. 3rd Canad. Conf. Comput. Geom., pages 141-144, 1991. Keyword(s): randomized algorithms, Delaunay triangulation, skeleton, medial axis, minimum spanning tree, simple polygon.


  87. O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. In Proc. 2nd Workshop Algorithms Data Struct., volume 519 of Lecture Notes in Computer Science, pages 42-53, 1991. Springer-Verlag. Keyword(s): randomized algorithms, Delaunay triangulation, dynamizing data structures.


  88. J.-D. Boissonnat, O. Devillers, and M. Teillaud. An on-line construction of higher-order Voronoi diagrams and its randomized analysis. In Proc. 2nd Canad. Conf. Comput. Geom., pages 278-281, 1990. Keyword(s): randomized algorithms, higher order Voronoi diagrams, dynamic algorithms.


Research reports
  1. Nicolas Broutin, Olivier Devillers, and Ross Hemsley. Efficiently Navigating a Random Delaunay Triangulation. Research Report 8464, INRIA, 2014. [WWW]


  2. Olivier Devillers, Philippe Duchon, and Rémy Thomasse. A generator of random convex polygons in a disc. Research Report 8467, INRIA, 2014. [WWW]


  3. Olivier Devillers, Marc Glisse, and Rémy Thomasse. A convex body with chaotic random convex hull. Research Report 8437, INRIA, 2013. [WWW]


  4. Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. Homological reconstruction and simplification in ${\mathbb R}^3$. Research Report 8169, INRIA, 2012. [WWW]


  5. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Research Report 8146, INRIA, 2012. [WWW]


  6. Nicolas Broutin, Olivier Devillers, and Ross Hemsley. A cone can help you find your way in a Poisson Delaunay triangulation. Research Report 8194, INRIA, 2012. [WWW]


  7. Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. Research Report 7989, INRIA, 2012. [WWW]


  8. Luca Castelli Aleardi, Olivier Devillers, and Jarek Rossignac. ESQ: Editable SQuad representation for triangle meshes. Research Report 8066, INRIA, 2012. [WWW]


  9. Olivier Devillers, Marc Glisse, and Xavier Goaoc. Complexity analysis of random geometric structures made simpler. Research Report 8168, INRIA, 2012. [WWW]


  10. Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, and Matthias Reitzner. The monotonicity of $f$-vectors of random polytopes. Research Report 8154, INRIA, 2012. [WWW]


  11. Olivier Devillers, Menelaos I. Karavelas, and Monique Teillaud. Qualitative Symbolic Perturbation: a new geometry-based perturbation framework. Research Report 8153, INRIA, 2012. [WWW]


  12. Luca Castelli Aleardi and Olivier Devillers. Explicit array-based compact data structures for triangulations. Research Report 7736, INRIA, 2011. [WWW]


  13. Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. Research Report 7299, INRIA, 2010. [WWW]


  14. Pedro Machado Manhães de Castro and Olivier Devillers. On the Size of Some Trees Embedded in $\mathbb{R}^d$. Research Report 7179, INRIA, 2010. [WWW]


  15. Pedro Machado Manhães de Castro and Olivier Devillers. Walking Faster in a Triangulation. Research Report 7322, INRIA, 2010. [WWW]


  16. Dominique Attali, Olivier Devillers, and Xavier Goaoc. The Effect of Noise on the Number of Extreme Points. Research Report 7134, INRIA, 2009. [WWW]


  17. Olivier Devillers. Vertex Removal in Two Dimensional Delaunay Triangulation: Asymptotic Complexity is Pointless. Research Report 7104, INRIA, 2009. [WWW]


  18. Pedro Machado Manhães de Castro and Olivier Devillers. Self-Adapting Point Location. Research Report 7132, INRIA, 2009. [WWW]


  19. Oswin Aichholzer, Franz Aurenhammer, Olivier Devillers, Thomas Hackl, Monique Teillaud, and Birgit Vogtenhuber. Counting Quadrics and Delaunay Triangulations and a new Convex Hull Theorem. Research Report 6748, INRIA, 2008. [WWW]


  20. Nina Amenta, Dominique Attali, and Olivier Devillers. A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron. Research Report 6522, INRIA, 2008. [WWW]


  21. Olivier Devillers. Géométrie algorithmique et réseaux. Research Report 6514, INRIA, 2008. [WWW]


  22. Olivier Devillers and Pedro Machado Manhães de Castro. State of the Art: Updating Delaunay Triangulations for Moving Points. Research Report 6665, INRIA, 2008. [WWW]


  23. Pedro Machado Manhães de Castro and Olivier Devillers. Delaunay Triangulations for Moving Points. Research Report 6750, INRIA, 2008. [WWW]


  24. Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, and Raimund Seidel. Between umbra and penumbra. Research Report 6347, INRIA, 2007. [WWW]


  25. Julien Demouth, Olivier Devillers, Marc Glisse, and Xavier Goaoc. Helly-type theorems for approximate covering. Research Report 6342, INRIA, 2007. [WWW]


  26. Olivier Devillers and Xavier Goaoc. Random sampling of a cylinder yields a not so nasty Delaunay triangulation. Research Report 6323, INRIA, 2007. [WWW]


  27. Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensionalpolyhedra. Research Report 5986, INRIA, 2006. [WWW]


  28. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Optimal Succinct Representations of Planar Maps. Research Report 5803, INRIA, 2006. [WWW]


  29. Olivier Devillers and Monique Teillaud. Perturbations and Vertex Removal in Delaunay and Regular 3D Triangulations. Research Report 5968, INRIA, 2006. [WWW]


  30. H. Brönnimann, O. Devillers, Vida Dujmovic, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra. Research Report 5671, INRIA, 2005. [WWW]


  31. Hervé Brönnimann, Olivier Devillers, Sylvain Lazard, and Frank Sottile. Lines tangent to four triangles in three-dimensional space. Research Report 5693, INRIA, 2005. [WWW]


  32. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Dynamic updates of succinct triangulations. Research Report 5709, INRIA, 2005. [WWW]


  33. Olivier Devillers, Vida Dujmovic, Hazel Everett, Samuel Hornus, Sue Whitesides, and Steve Wismath. Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint. Research Report 5742, INRIA, 2005. [WWW]


  34. Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, and Stephen Wismath. Drawing $K_n$ in Three Dimensions with One Bend per Edge. Research Report 5708, INRIA, 2005. [WWW]


  35. Abdelkrim Mebarki, Pierre Alliez, and Olivier Devillers. Farthest Point Seeding for Placement of Streamlines. Research Report 5524, INRIA, 2005. [WWW]


  36. Luca Castelli Aleardi and Olivier Devillers. Canonical Triangulation of a Graph, with a Coding Application. Research Report 5231, INRIA, 2004. [WWW]


  37. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Compact representation of triangulations. Research Report 5433, INRIA, 2004. [WWW]


  38. François Cayre, Olivier Devillers, Francis Schmitt, and Henri Maître. Watermarking 3D triangle meshes for authentication and integrity. Research Report 5223, INRIA, 2004. [WWW]


  39. Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun. Anisotropic Polygonal Remeshing. Research Report 4808, INRIA, 2003. Note: ECG-TR-244104-02. [WWW]


  40. Olivier Devillers and Philippe Guigue. Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions. Research Report 5070, INRIA, 2003. [WWW]


  41. Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. Isotropic Surface Remeshing. Research Report 4594, INRIA, 2002. Note: ECG-TR-184100-01. [WWW]


  42. Olivier Devillers, Vida Dujmovic, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, and Sylvain Petitjean. The expected number of 3D visibility events is linear. Research Report 4671, INRIA, 2002. Note: ECG-TR-241107-01. [WWW]


  43. Olivier Devillers and Philippe Guigue. Faster Triangle-Triangle Intersection Tests. Research Report 4488, INRIA, 2002. [WWW]


  44. Olivier Devillers and Philippe Guigue. Finite Precision Elementary Geometric Constructions. Research Report 4559, INRIA, 2002. Note: ECG-TR-122100-01. [WWW]


  45. Olivier Devillers, Ferran Hurtado, and Carlos Seara. Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position. Research Report 4352, INRIA, 2002. [WWW]


  46. Olivier Devillers and Sylvain Pion. Efficient Exact Geometric Predicates for Delaunay Triangulations. Research Report 4351, INRIA, 2002. Note: ECG-TR-123102-01. [WWW]


  47. Olivier Devillers and Monique Teillaud. Perturbations and Vertex Removal in a 3D Delaunay Triangulation. Research Report 4624, INRIA, 2002. [WWW]


  48. Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristán, and Monique Teillaud. Splitting a Delaunay Triangulation in Linear Time. Research Report 4160, INRIA, 2001. [WWW]


  49. Olivier Devillers. The Number of Cylindrical Shells. Research Report 4234, INRIA, 2001. [WWW]


  50. Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, and Vera Sacristán. Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction. Research Report 4119, INRIA, 2001. [WWW]


  51. Olivier Devillers and Pierre-Marie Gandoin. Compression interactive de maillages triangulaires arbitraires. Research Report 4158, INRIA, 2001. [WWW]


  52. Olivier Devillers, Bernard Mourrain, Franco P. Preparata, and Philippe Trebuchet. On circular Cylinders by Four or Five Points in Space. Research Report 4195, INRIA, 2001. [WWW]


  53. Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Research Report 4120, INRIA, 2001. [WWW]


  54. Olivier Devillers and Franco P. Preparata. Culling a Set of Points for Roundness or Cylindricity Evaluations. Research Report 4159, INRIA, 2001. [WWW]


  55. Olivier Devillers and Pierre-Marie Gandoin. Geometric Compression for Interactive Transmission. Research Report 3910, INRIA, 2000. [WWW]


  56. Olivier Devillers and Philippe Guigue. Le tampon mélangeur. Research Report 3988, INRIA, 2000. [WWW]


  57. Hervé Brönnimann and Olivier Devillers. The union of unit balls has quadratic complexity, even if they all contain the origin. Research Report 3758, INRIA, 1999. [WWW]


  58. Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Exact predicates for circle arcs arrangements. Research Report 3826, INRIA, 1999. [WWW]


  59. Olivier Devillers and Pierre-Marie Gandoin. Compression géométrique pour une transmission progressive. Research Report 3766, INRIA, 1999. [WWW]


  60. Olivier Devillers and Franco P. Preparata. Evaluating the cylindricity of a nominally cylindrical point set. Research Report 3747, INRIA, 1999. [WWW]


  61. O. Devillers. Computational geometry and discrete computations. Research Report 3533, INRIA, 1998. [WWW]


  62. O. Devillers. On Deletion in Delaunay Triangulation. Research Report 3451, INRIA, 1998. [WWW]


  63. O. Devillers and P.-M. Gandoin. Rounding Voronoi Diagram. Research Report 3481, INRIA, 1998. [WWW]


  64. O. Devillers, G. Liotta, F. P. Preparata, and R. Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Research Report 3527, INRIA, 1998. [WWW]


  65. Olivier Devillers and Asish Mukhopadhyay. Finding an ordinary conic and more. Research Report 3517, INRIA, 1998. [WWW]


  66. O. Devillers and F. P. Preparata. Further Results on Arithmetic Filters for Geometric Predicates. Research Report 3528, INRIA, 1998. [WWW]


  67. P. Alliez, O. Devillers, and J. Snoeyink. Removing Degeneracies by Perturbing the Problem or the World. Research Report 3316, INRIA, 1997. [WWW]


  68. Jean-Daniel Boissonnat, Olivier Devillers, and Sylvain Lazard. Motion planning of legged robots. Research Report 3214, INRIA, 1997. [WWW]


  69. O. Devillers. Improved incremental randomized Delaunay triangulation. Research Report 3298, INRIA, 1997. [WWW]


  70. O. Devillers and M. Katz. Optimal Line Bipartitions of Point Sets. Research Report 2871, INRIA, 1996. [WWW]


  71. O. Devillers and F. P. Preparata. A probabilistic analysis of the power of arithmetic filters. Research Report 2971, INRIA, 1996. Note: Also report CS96-27 Brown University. [WWW]


  72. L. Tancredi, M. Teillaud, and O. Devillers. Symbolic Elimination for parallel manipulators. Research Report 2809, INRIA, 1996. [WWW] Keyword(s): parallel manipulator, forward kinematics problem, algebraic geometry.


  73. Mark de Berg, Otfried Cheong, Olivier Devillers, Marc van Kreveld, and Monique Teillaud. Computing the Maximum Overlap of Two Convex Polygons Under Translations. Research Report 2832, INRIA, 1996. [WWW]


  74. J-D. Boissonnat, J. Czyzowicz, O. Devillers, J. Urrutia, and M. Yvinec. Computing Largest Circles Separating Two Sets of Segments. Research Report 2705, INRIA, 1995. [WWW]


  75. M. de Berg, O. Devillers, K. Dobrindt, and O. Schwarzkopf. Computing a single cell in the union of two simple polygons. Research Report 2626, INRIA, 1995. [WWW]


  76. F. Avnaim, J-D. Boissonnat, O. Devillers, F. P. Preparata, and M. Yvinec. Evaluating signs of determinants using single-precision arithmetic. Research Report 2306, INRIA, 1994. [WWW]


  77. J-D. Boissonnat, J. Czyzowicz, O. Devillers, J-M. Robert, and M. Yvinec. Convex Tours of Bounded Curvature. Research Report 2375, INRIA, 1994. [WWW]


  78. J-D. Boissonnat, J. Czyzowicz, O. Devillers, and M. Yvinec. Circular Separability of Polygons. Research Report 2406, INRIA, 1994. [WWW]


  79. O. Devillers and M. Golin. Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems. Research Report 2263, INRIA, 1994. [WWW]


  80. O. Devillers and M. Golin. Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Research Report 2280, INRIA, 1994. [WWW]


  81. O. Devillers, M. Golin, K. Kedem, and S. Schirra. Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points. Research Report 2329, INRIA, 1994. [WWW]


  82. J-D. Boissonnat, A. Cérézo, O. Devillers, J. Duquesne, and M. Yvinec. An Algorithm for Constructing the Convex Hull of a Set of Spheres in Dimension $d$. Research Report 2080, INRIA, 1993. [WWW]


  83. O. Devillers and A. Fabri. Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. Research Report 1882, INRIA, 1993. [WWW]


  84. J.-D. Boissonnat, O. Devillers, L. Donati, and F. P. Preparata. Motion planning for a spider robot. Research Report 1767, INRIA, 1992. [WWW] Keyword(s): motion plannig, legged robot.


  85. O. Devillers. Robust and efficient implementation of the Delaunay tree. Research Report 1619, INRIA, 1992. [WWW] Keyword(s): randomized algorithms, Delaunay triangulation, practical issue, degenerate cases.


  86. O. Devillers, S. Meiser, and M. Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. Research Report 1620, INRIA, 1992. [WWW] Keyword(s): duality results, generalized Voronoi diagrams, geometric transforms, upper lower envelopes.


  87. J.-D. Boissonnat, A. Cérézo, O. Devillers, and M. Teillaud. Output-sensitive construction of the $3$-d Delaunay triangulation of constrained sets of points. Research Report 1415, INRIA, 1991. [WWW] Keyword(s): Delaunay triangulation, Voronoi diagrams, output-sensitive algorithms, shape reconstructions, shelling, tomography.


  88. O. Devillers. Randomization yields simple $O(n\log^{\star} n)$ algorithms for difficult $\Omega(n)$ problems. Research Report 1412, INRIA, 1991. [WWW]


  89. O. Devillers, M. Teillaud, and M. Yvinec. Dynamic location in an arrangement of line segments in the plane. Research Report 1558, INRIA, 1991. [WWW]


  90. J-D. Boissonnat, O. Devillers, and F. P. Preparata. Union of 3-colored triangles. Research Report 1293, INRIA, 1990. [WWW]


  91. J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Research Report 1285, INRIA, 1990. [WWW] Keyword(s): randomized algorithms, Voronoi, Delaunay, trapezoidal map, dynamic algorithms.


  92. J.-D. Boissonnat, O. Devillers, and M. Teillaud. A dynamic construction of higher-order Voronoi diagrams and its randomized analysis. Research Report 1207, INRIA, 1990. [WWW] Keyword(s): randomized algorithms, higher order Voronoi diagrams, dynamic algorithms.


  93. O. Devillers. Simultaneous containment of several polygons: analysis of the contact configurations. Research Report 1179, INRIA, 1990. [WWW] Keyword(s): polygon placement, contact configurations.


  94. O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Research Report 1349, INRIA, 1990. [WWW]


Manuals, booklets
  1. O. Devillers, A. Fabri, E. Flato, W. Freiseisen, B. Gärtner, G.-J. Giezeman, D. Halperin, M. Hoffmann, L. Kettner, G. Neyer, S. Har Peled, R. Rickenbach, S. Schirra, S. Schönherr, M. Teillaud, C. Vam Geem, R. Veltkamp, W. Wesselink, and M. Yvinec. The CGAL Reference Manual. Part 2: Basic Library. 1997. Note: Release 0.9. [WWW]


Miscellaneous
  1. Olivier Devillers. Un joli algorithme géométrique et ses vilains problèmes numériques, 2006. Note: Interstices web site, http://www.interstices.info/algorithme-geometrique. [WWW]


  2. Olivier Devillers, Ferran Hurtado, and Carlos Seara. Chromatic Variants of the Erdös-Szekeres Theorem on Points in Convex Position, 2002. Note: 18th European Workshop Comput. Geom.


  3. Olivier Devillers, Alexandra Fronville, Bernard Mourrain, and Monique Teillaud. Exact predicates for circle arcs arrangements, 2000. Note: 16th European Workshop Comput. Geom.


  4. Olivier Devillers and Pierre-Marie Gandoin. Compression géométrique pour une transmission progressive, 1999. Note: 12ème journées de l'AFIG.


  5. Olivier Devillers and Franco P. Preparata. Further Results on Arithmetic Filters for Geometric Predicates, 1999. Note: 15th European Workshop Comput. Geom., pp 113--116.


  6. Olivier Devillers, François Rebufat, and Monique Teillaud. Cours CGAL, 1999. Note: Barcelone. [WWW]


  7. O. Devillers. GéDéoN, 1996. Note: 26 numéros de 1991 à 1996. [WWW]


  8. L. Tancredi, M. Teillaud, and O. Devillers. Symbolic Elimination for parallel manipulators, 1996. Note: Communication at 4th Internat. Sympos. on Effective Methods in Algebraic Geometry (MEGA).



BACK TO INDEX




Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.




Last modified: Mon Sep 29 16:15:56 2014
Author: odevil.


This document was translated from BibTEX by bibtex2html