Edit Profile (opens in new tab) Devillers, Olivier Co-Author Distance Author ID: devillers.olivier Published as: Devillers, Olivier; Devillers, O. External Links: MGP Documents Indexed: 121 Publications since 1991, including 2 Additional arXiv Preprints 1 Contribution as Editor Co-Authors: 99 Co-Authors with 114 Joint Publications 2,513 Co-Co-Authors all top 5 Co-Authors 8 single-authored 20 Glisse, Marc 20 Teillaud, Monique 19 Boissonnat, Jean-Daniel 17 Lazard, Sylvain 11 Preparata, Franco P. 10 Goaoc, Xavier 9 Yvinec, Mariette 8 Everett, Hazel 6 Attali, Dominique 6 Castelli Aleardi, Luca 5 De Castro, Pedro Machado Manhães 5 Whitesides, Sue H. 4 Alliez, Pierre 4 Cheong, Otfried 4 Czyzowicz, Jurek 4 Demouth, Julien 4 Dujmović, Vida 4 Hurtado, Ferran 4 Liotta, Giuseppe 4 Wismath, Stephen K. 3 Brönnimann, Hervé 3 de Berg, Mark Theodoor 3 Golin, Mordecai J. 3 Guigue, Philippe 3 Hemsley, Ross 3 Mourrain, Bernard 3 Na, Hyeon-Suk 3 Pion, Sylvain 3 Sacristán, Vera 3 Schaeffer, Gilles 2 Amenta, Nina 2 Bauer, Ulrich 2 Bogdanov, Mikhail 2 Bremner, David 2 Broutin, Nicolas 2 Cerezo, André 2 Chazelle, Bernard 2 Chenavier, Nicolas 2 Dutta, Kunal 2 Fabri, Andreas 2 Fronville, Alexandra 2 Fusy, Éric 2 Gandoin, Pierre-Marie 2 Hornus, Samuel 2 Karavelas, Menelaos I. 2 Katz, Matthew J. 2 Lenhart, William J. 2 Lieutier, André 2 Mchedlidze, Tamara 2 Meiser, Stefan 2 Mora, Mercè 2 Moroz, Guillaume 2 Pentcheva, Maria 2 Ramos, Pedro A. 2 Seidel, Raimund 2 Tamassia, Roberto 2 Thomasse, Rémy 2 Tournois, Jane 2 van Kreveld, Marc J. 1 Aleardi, L. Castelli 1 Avnaim, Francis 1 Brose, Prosenjit 1 Buchin, Kevin 1 Chen, Dan 1 Cheng, Siu-Wing 1 Colin de Verdière, Éric 1 de Carufel, Jean-Lou 1 Despré, Vincent 1 Dobrindt, Katrin T. G. 1 Donati, Leonbattista 1 Duquesne, Jacqueline 1 Erickson, Jeff 1 Estkowski, Regina 1 Iacono, John 1 Isenburg, Martin 1 Károlyi, Gyula 1 Kedem, Klara 1 Langerman, Stefan 1 Mebarki, Abdelkrim 1 Morin, Pat 1 Mukhopadhyay, Asish Kumar 1 Mulzer, Wolfgang Johann Heinrich 1 Noizet, Louis 1 Park, Jiwon 1 Parlier, Hugo 1 Petitjean, Sylvain 1 Reitzner, Matthias 1 Robert, Jean-Marc 1 Schirra, Stefan 1 Schlenker, Jean-Marc 1 Schott, René 1 Schrijvers, Okke 1 Seara, Carlos 1 Shewchuk, Jonathan Richard 1 Snoeyink, Jack Scott 1 Sottile, Frank 1 Trébuchet, Philippe 1 Urrutia Galicia, Jorge L. 1 Wismath, Steve all top 5 Serials 17 International Journal of Computational Geometry & Applications 15 Computational Geometry 10 Discrete & Computational Geometry 10 Journal of Computational Geometry 4 Algorithmica 3 SIAM Journal on Computing 3 Theoretical Computer Science 2 Information Processing Letters 2 International Journal of Foundations of Computer Science 1 Advances in Applied Probability 1 Periodica Mathematica Hungarica 1 Operations Research Letters 1 Computer Aided Geometric Design 1 Random Structures & Algorithms 1 Nordic Journal of Computing 1 Reliable Computing 1 Electronic Communications in Probability 1 Theory of Computing Systems 1 Journal of Graph Algorithms and Applications 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 Graphical Models 1 Numerical Mathematics: Theory, Methods and Applications all top 5 Fields 98 Computer science (68-XX) 33 Convex and discrete geometry (52-XX) 23 Numerical analysis (65-XX) 9 Combinatorics (05-XX) 6 Probability theory and stochastic processes (60-XX) 4 Geometry (51-XX) 4 Operations research, mathematical programming (90-XX) 3 Manifolds and cell complexes (57-XX) 2 Geophysics (86-XX) 1 General and overarching topics; collections (00-XX) 1 Algebraic topology (55-XX) 1 Statistics (62-XX) 1 Mechanics of particles and systems (70-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 92 Publications have been cited 442 times in 339 Documents Cited by ▼ Year ▼ Applications of random sampling to on-line algorithms in computational geometry. Zbl 0769.68118 Boissonnat, Jean-Daniel; Devillers, Olivier; Schott, René; Teillaud, Monique; Yvinec, Mariette 28 1992 Chromatic variants of the Erdős–Szekeres theorem on points in convex position. Zbl 1034.52014 Devillers, Olivier; Hurtado, Ferran; Károlyi, Gyula; Seara, Carlos 21 2003 Succinct representations of planar maps. Zbl 1157.68066 Aleardi, L. Castelli; Devillers, O.; Schaeffer, G. 18 2008 Triangulations in CGAL. Zbl 1016.68138 Boissonnat, Jean-Daniel; Devillers, Olivier; Pion, Sylvain; Teillaud, Monique; Yvinec, Mariette 16 2002 Succinct representation of triangulations with a boundary. Zbl 1161.68396 Castelli Aleardi, L.; Devillers, Olivier; Schaeffer, Gilles 15 2005 Randomization yields simple \(O(n\log{}^*n)\) algorithms for difficult \({\Omega{}}(n)\) problems. Zbl 0761.68094 Devillers, Olivier 15 1992 Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. Zbl 1380.68382 Boissonnat, Jean-Daniel; Devillers, Olivier; Hornus, Samuel 15 2009 Computing the maximum overlap of two convex polygons under translations. Zbl 0910.68226 de Berg, M.; Cheong, O.; Devillers, O.; van Kreveld, M.; Teillaud, M. 13 1998 The Delaunay hierarchy. Zbl 1066.68138 Devillers, Olivier 12 2002 Centroidal Voronoi diagrams for isotropic surface remeshing. Zbl 1101.68897 Alliez, Pierre; Colin de Verdiére, Éric; Devillers, Olivier; Isenburg, Martin 12 2005 Checking the convexity of polytopes and the planarity of subdivisions. Zbl 0921.68101 Devillers, Olivier; Liotta, Giuseppe; Preparata, Franco P.; Tamassia, Roberto 11 1998 Walking in a triangulation. Zbl 1066.68139 Devillers, Olivier; Pion, Sylvain; Teillaud, Monique 11 2002 Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. Zbl 1302.68272 Amenta, Nina; Attali, Dominique; Devillers, Olivier 11 2007 Fully dynamic Delaunay triangulation in logarithmic expected per operation. Zbl 0773.68066 Devillers, Olivier; Meiser, Stefan; Teillaud, Monique 10 1992 A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Zbl 0780.68109 Boissonnat, Jean-Daniel; Devillers, Olivier; Teillaud, Monique 10 1993 Walking in a triangulation. Zbl 1374.68659 Devillers, Olivier; Pion, Sylvain; Teillaud, Monique 10 2001 Evaluating signs of determinants using single-precision arithmetic. Zbl 0865.68119 Avnaim, Francis; Boissonnat, Jean-Daniel; Devillers, Olivier; Preparata, Franco P.; Yvinec, Mariette 9 1997 Computing largest circles separating two sets of segments. Zbl 1074.68631 Boissonnat, Jean-Daniel; Czyzowicz, Jurek; Devillers, Olivier; Urrutia, Jorge; Yvinec, Mariette 8 2000 Splitting a Delaunay triangulation in linear time. Zbl 1016.68137 Chazelle, B.; Devillers, O.; Hurtado, F.; Mora, M.; Sacristan, V. 8 2002 2D centroidal Voronoi tessellations with constraints. Zbl 1224.65053 Tournois, Jane; Alliez, Pierre; Devillers, Olivier 7 2010 A probabilistic analysis of the power of arithmetic filters. Zbl 0912.68204 Devillers, O.; Preparata, F. P. 7 1998 Optimal succinct representations of planar maps. Zbl 1153.68515 Aleardi, Luca Castelli; Devillers, Olivier; Schaeffer, Gilles 7 2006 Queries on Voronoi diagrams on moving points. Zbl 0857.68104 Devillers, O.; Golin, M.; Kedem, K.; Schirra, S. 7 1996 An algorithm for constructing the convex hull of a set of spheres in dimension \(d\). Zbl 0849.68125 Boissonnat, Jean-Daniel; Cérézo, André; Devillers, Olivier; Duquesne, Jacqueline; Yvinec, Mariette 6 1996 Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Zbl 1016.68142 Devillers, Olivier; Fronville, Alexandra; Mourrain, Bernard; Teillaud, Monique 6 2002 Circular cylinders through four or five points in space. Zbl 1031.52008 Devillers, Olivier; Mourrain, Bernard; Preparata, Franco P.; Trebuchet, Philippe 6 2003 The monotonicity of \(f\)-vectors of random polytopes. Zbl 1359.60024 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Moroz, Guillaume; Reitzner, Matthias 6 2013 Interleaving Delaunay refinement and optimization for 2D triangle mesh generation. Zbl 1134.65329 Tournois, Jane; Alliez, Pierre; Devillers, Olivier 5 2008 Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. Zbl 1138.65019 Brönnimann, Hervé; Devillers, Olivier; Dujmović, Vida; Everett, Hazel; Glisse, Marc; Goaoc, Xavier; Lazard, Sylvain; Na, Hyeon-Suk; Whitesides, Sue 5 2007 Dog bites postman: Point location in the moving Voronoi diagram and related problems. Zbl 1035.68528 Devillers, Olivier; Golin, Mordecai J. 5 1998 Removing degeneracies by perturbing the problem or perturbing the world. Zbl 0996.65019 Alliez, Pierre; Devillers, Olivier; Snoeyink, Jack 5 2000 Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Zbl 0875.68901 Devillers, Olivier; Golin, Mordecai J. 5 1995 Perturbations for Delaunay and weighted Delaunay 3D triangulations. Zbl 1206.65079 Devillers, Olivier; Teillaud, Monique 4 2011 Further results on arithmetic filters for geometric predicates. Zbl 0944.68182 Devillers, Olivier; Preparata, Franco P. 4 1999 Perturbations and vertex removal in a 3D Delaunay triangulation. Zbl 1094.68679 Devillers, Olivier; Teillaud, Monique 4 2003 Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Zbl 1374.68658 Devillers, Olivier; Fronville, Alexandra; Mourrain, Bernard; Teillaud, Monique 4 2000 Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity. Zbl 1431.60012 Chenavier, Nicolas; Devillers, Olivier 4 2018 Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Zbl 0765.68204 Devillers, Olivier; Meiser, Stefan; Teillaud, Monique 3 1991 Optimal line bipartitions of point sets. Zbl 1026.65011 Devillers, Olivier; Katz, Matthew J. 3 1999 The expected number of 3D visibility events is linear. Zbl 1041.68107 Devillers, Olivier; Dujmovic, Vida; Everett, Hazel; Goaoc, Xavier; Lazard, Sylvain; Na, Hyeon-Suk; Petitjean, Sylvain 3 2003 Computing roundness is easy if the set is almost round. Zbl 1152.68664 Devillers, Olivier; Ramos, Pedro A. 3 2002 Minimal set of constraints for 2D constrained Delaunay reconstruction. Zbl 1093.68126 Devillers, Olivier; Estkowski, Regina; Gandoin, Pierre-Marie; Hurtado, Ferran; Ramos, Pedro; Sacristán, Vera 3 2003 Triangulations in CGAL (extended abstract). Zbl 1374.68643 Boissonnat, Jean-Daniel; Devillers, Olivier; Teillaud, Monique; Yvinec, Mariette 3 2000 Efficiently navigating a random Delaunay triangulation. Zbl 1331.68246 Broutin, Nicolas; Devillers, Olivier; Hemsley, Ross 3 2014 The worst visibility walk in a random Delaunay triangulation is \(O(\sqrt n)\). Zbl 1405.68411 Devillers, Olivier; Hemsley, Ross 3 2016 Smoothed complexity of convex hulls by witnesses and collectors. Zbl 1405.68410 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Thomasse, Rémy 3 2016 Delaunay triangulation of imprecise points, preprocess and actually get a fast query time. Zbl 1404.68187 Devillers, Olivier 3 2011 Array-based compact data structures for triangulations: practical solutions with theoretical guarantees. Zbl 1426.68267 Aleardi, Luca Castelli; Devillers, Olivier 3 2018 Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs. Zbl 1477.68542 Brose, Prosenjit; De Carufel, Jean-Lou; Devillers, Olivier 3 2020 Oja centers and centers of gravity. Zbl 1320.62119 Chen, Dan; Devillers, Olivier; Iacono, John; Langerman, Stefan; Morin, Pat 3 2013 Maintaining visibility information of planar point sets with a moving viewpoint. Zbl 1145.65011 Devillers, Olivier; Dujmović, Vida; Everett, Hazel; Hornus, Samuel; Whitesides, Sue; Wismath, Steve 2 2007 Evaluating the cylindricity of a nominally cylindrical point set. Zbl 0953.65011 Devillers, Olivier; Preparata, Franco P. 2 2000 Qualitative symbolic perturbation: two applications of a new geometry-based perturbation framework. Zbl 1393.68172 Devillers, Olivier; Karavelas, Menelaos; Teillaud, Monique 2 2017 On the complexity of umbra and penumbra. Zbl 1194.65036 Demouth, J.; Devillers, O.; Everett, H.; Glisse, M.; Lazard, S.; Seidel, R. 2 2009 Circular separability of polygons. Zbl 0984.68175 Boissonnat, Jean-Daniel; Czyzowicz, Jurek; Devillers, Olivier; Yvinec, Mariette 2 2001 On deletion in Delaunay triangulations. Zbl 1152.68663 Devillers, Olivier 2 2002 Computing the union of 3-colored triangles. Zbl 0735.68083 Boissonnat, Jean-Daniel; Devillers, Olivier; Preparata, Franco P. 2 1991 Recognizing shrinkable complexes is NP-complete. Zbl 1405.68394 Attali, Dominique; Devillers, Olivier; Glisse, Marc; Lazard, Sylvain 2 2016 Monotone simultaneous embeddings of paths in \(d\) dimensions. Zbl 1478.68220 Bremner, David; Devillers, Olivier; Glisse, Marc; Lazard, Sylvain; Liotta, Giuseppe; Mchedlidze, Tamara; Whitesides, Sue; Wismath, Stephen 2 2016 Efficiently navigating a random Delaunay triangulation. Zbl 1344.05050 Broutin, Nicolas; Devillers, Olivier; Hemsley, Ross 2 2016 Walking in a planar Poisson-Delaunay triangulation: shortcuts in the Voronoi path. Zbl 1434.60130 Devillers, Olivier; Noizet, Louis 2 2018 Lines tangent to four triangles in three-dimensional space. Zbl 1117.52007 Brönnimann, H.; Devillers, O.; Lazard, S.; Sottile, F. 1 2007 Vertex removal in two-dimensional Delaunay triangulation: speed-up by low degrees optimization. Zbl 1206.65078 Devillers, Olivier 1 2011 On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\). Zbl 1211.90267 de Castro, Pedro M. M.; Devillers, Olivier 1 2011 Explicit array-based compact data structures for triangulations. Zbl 1350.68065 Castelli Aleardi, Luca; Devillers, Olivier 1 2011 Finding an ordinary conic and an ordinary hyperplane. Zbl 0938.68877 Devillers, Olivier; Mukhopadhyay, Asish 1 1999 Helly-type theorems for approximate covering. Zbl 1178.52004 Demouth, Julien; Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2009 Splitting a Delaunay triangulation in linear time. Zbl 1006.68560 Chazelle, Bernard; Devillers, Olivier; Hurtado, Ferran; Mora, Mercè; Sacristán, Vera; Teillaud, Monique 1 2001 Culling a set of points for roundness or cylindricity evaluations. Zbl 1074.68637 Devillers, Olivier; Preparata, Franco P. 1 2003 Drawing \(K_n\) in three dimensions with one bend per edge. Zbl 1171.68602 Devillers, Olivier; Everett, Hazel; Lazard, Sylvain; Pentcheva, Maria; Wismath, Stephen K. 1 2006 Helly-type theorems for approximate covering. Zbl 1221.52014 Demouth, Julien; Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2008 The shuffling buffer. Zbl 1074.68636 Devillers, Olivier; Guigue, Philippe 1 2001 An introduction to randomization in computational geometry. Zbl 0871.68166 Devillers, Olivier 1 1996 Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. Zbl 0871.68178 Fabri, Andreas; Devillers, Olivier 1 1996 Catalog-based representation of 2D triangulations. Zbl 1241.68121 Aleardi, Luca Castelli; Devillers, Olivier; Mebarki, Abdelkrim 1 2011 A tight bound for the Delaunay triangulation of points on a polyhedron. Zbl 1254.51010 Amenta, Nina; Attali, Dominique; Devillers, Olivier 1 2012 The number of lines tangent to arbitrary convex polyhedra in 3D. Zbl 1374.68645 Brönnimann, H.; Devillers, O.; Dujmović, V.; Everett, H.; Glisse, M.; Goaoc, X.; Lazard, S.; Na, H.-S.; Whitesides, S. 1 2004 Inner and outer rounding of set operations on lattice polygonal regions. Zbl 1378.65054 Devillers, Olivier; Guigue, Philippe 1 2004 On the smoothed complexity of convex hulls. Zbl 1378.68170 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Thomasse, Rémy 1 2015 Qualitative symbolic perturbation. Zbl 1387.68254 Devillers, Olivier; Karavelas, Menelaos; Teillaud, Monique 1 2016 Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Zbl 1305.68207 Bogdanov, Mikhail; Devillers, Olivier; Teillaud, Monique 1 2013 Complexity analysis of random geometric structures made simpler. Zbl 1305.68102 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2013 Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Zbl 1404.68183 Bogdanov, Mikhail; Devillers, Olivier; Teillaud, Monique 1 2014 Computing a single cell in the overlay of two simple polygons. Zbl 1336.68269 de Berg, Mark; Devillers, Olivier; Dobrindt, Katrin; Schwarzkopf, Otfried 1 1997 Empty-ellipse graphs. Zbl 1192.52020 Devillers, Olivier; Erickson, Jeff; Goaoc, Xavier 1 2008 Simple and efficient distribution-sensitive point location in triangulations. Zbl 1430.68379 Machado Manhães De Castro, Pedro; Devillers, Olivier 1 2011 Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cyclinder and torus. Zbl 1418.68166 Castelli Aleardi, Luca; Devillers, Olivier; Fusy, Éric 1 2018 Vertex deletion for 3D Delaunay triangulations. Zbl 1394.68413 Buchin, Kevin; Devillers, Olivier; Mulzer, Wolfgang; Schrijvers, Okke; Shewchuk, Jonathan 1 2013 Optimal line bipartitions of point sets. Zbl 1512.68412 Devillers, Olivier; Katz, Matthew J. 1 1996 Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. Zbl 1377.68263 Castelli Aleardi, Luca; Devillers, Olivier; Fusy, Éric 1 2013 A pedagogic JavaScript program for point location strategies. Zbl 1283.68355 Devillers, Olivier; de Castro, Pedro Machado Manhães 1 2011 Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation. Zbl 1428.60025 de Castro, Pedro Machado Manhães; Devillers, Olivier 1 2018 Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs. Zbl 1477.68542 Brose, Prosenjit; De Carufel, Jean-Lou; Devillers, Olivier 3 2020 Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity. Zbl 1431.60012 Chenavier, Nicolas; Devillers, Olivier 4 2018 Array-based compact data structures for triangulations: practical solutions with theoretical guarantees. Zbl 1426.68267 Aleardi, Luca Castelli; Devillers, Olivier 3 2018 Walking in a planar Poisson-Delaunay triangulation: shortcuts in the Voronoi path. Zbl 1434.60130 Devillers, Olivier; Noizet, Louis 2 2018 Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cyclinder and torus. Zbl 1418.68166 Castelli Aleardi, Luca; Devillers, Olivier; Fusy, Éric 1 2018 Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation. Zbl 1428.60025 de Castro, Pedro Machado Manhães; Devillers, Olivier 1 2018 Qualitative symbolic perturbation: two applications of a new geometry-based perturbation framework. Zbl 1393.68172 Devillers, Olivier; Karavelas, Menelaos; Teillaud, Monique 2 2017 The worst visibility walk in a random Delaunay triangulation is \(O(\sqrt n)\). Zbl 1405.68411 Devillers, Olivier; Hemsley, Ross 3 2016 Smoothed complexity of convex hulls by witnesses and collectors. Zbl 1405.68410 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Thomasse, Rémy 3 2016 Recognizing shrinkable complexes is NP-complete. Zbl 1405.68394 Attali, Dominique; Devillers, Olivier; Glisse, Marc; Lazard, Sylvain 2 2016 Monotone simultaneous embeddings of paths in \(d\) dimensions. Zbl 1478.68220 Bremner, David; Devillers, Olivier; Glisse, Marc; Lazard, Sylvain; Liotta, Giuseppe; Mchedlidze, Tamara; Whitesides, Sue; Wismath, Stephen 2 2016 Efficiently navigating a random Delaunay triangulation. Zbl 1344.05050 Broutin, Nicolas; Devillers, Olivier; Hemsley, Ross 2 2016 Qualitative symbolic perturbation. Zbl 1387.68254 Devillers, Olivier; Karavelas, Menelaos; Teillaud, Monique 1 2016 On the smoothed complexity of convex hulls. Zbl 1378.68170 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Thomasse, Rémy 1 2015 Efficiently navigating a random Delaunay triangulation. Zbl 1331.68246 Broutin, Nicolas; Devillers, Olivier; Hemsley, Ross 3 2014 Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Zbl 1404.68183 Bogdanov, Mikhail; Devillers, Olivier; Teillaud, Monique 1 2014 The monotonicity of \(f\)-vectors of random polytopes. Zbl 1359.60024 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Moroz, Guillaume; Reitzner, Matthias 6 2013 Oja centers and centers of gravity. Zbl 1320.62119 Chen, Dan; Devillers, Olivier; Iacono, John; Langerman, Stefan; Morin, Pat 3 2013 Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Zbl 1305.68207 Bogdanov, Mikhail; Devillers, Olivier; Teillaud, Monique 1 2013 Complexity analysis of random geometric structures made simpler. Zbl 1305.68102 Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2013 Vertex deletion for 3D Delaunay triangulations. Zbl 1394.68413 Buchin, Kevin; Devillers, Olivier; Mulzer, Wolfgang; Schrijvers, Okke; Shewchuk, Jonathan 1 2013 Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. Zbl 1377.68263 Castelli Aleardi, Luca; Devillers, Olivier; Fusy, Éric 1 2013 A tight bound for the Delaunay triangulation of points on a polyhedron. Zbl 1254.51010 Amenta, Nina; Attali, Dominique; Devillers, Olivier 1 2012 Perturbations for Delaunay and weighted Delaunay 3D triangulations. Zbl 1206.65079 Devillers, Olivier; Teillaud, Monique 4 2011 Delaunay triangulation of imprecise points, preprocess and actually get a fast query time. Zbl 1404.68187 Devillers, Olivier 3 2011 Vertex removal in two-dimensional Delaunay triangulation: speed-up by low degrees optimization. Zbl 1206.65078 Devillers, Olivier 1 2011 On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\). Zbl 1211.90267 de Castro, Pedro M. M.; Devillers, Olivier 1 2011 Explicit array-based compact data structures for triangulations. Zbl 1350.68065 Castelli Aleardi, Luca; Devillers, Olivier 1 2011 Catalog-based representation of 2D triangulations. Zbl 1241.68121 Aleardi, Luca Castelli; Devillers, Olivier; Mebarki, Abdelkrim 1 2011 Simple and efficient distribution-sensitive point location in triangulations. Zbl 1430.68379 Machado Manhães De Castro, Pedro; Devillers, Olivier 1 2011 A pedagogic JavaScript program for point location strategies. Zbl 1283.68355 Devillers, Olivier; de Castro, Pedro Machado Manhães 1 2011 2D centroidal Voronoi tessellations with constraints. Zbl 1224.65053 Tournois, Jane; Alliez, Pierre; Devillers, Olivier 7 2010 Incremental construction of the Delaunay triangulation and the Delaunay graph in medium dimension. Zbl 1380.68382 Boissonnat, Jean-Daniel; Devillers, Olivier; Hornus, Samuel 15 2009 On the complexity of umbra and penumbra. Zbl 1194.65036 Demouth, J.; Devillers, O.; Everett, H.; Glisse, M.; Lazard, S.; Seidel, R. 2 2009 Helly-type theorems for approximate covering. Zbl 1178.52004 Demouth, Julien; Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2009 Succinct representations of planar maps. Zbl 1157.68066 Aleardi, L. Castelli; Devillers, O.; Schaeffer, G. 18 2008 Interleaving Delaunay refinement and optimization for 2D triangle mesh generation. Zbl 1134.65329 Tournois, Jane; Alliez, Pierre; Devillers, Olivier 5 2008 Helly-type theorems for approximate covering. Zbl 1221.52014 Demouth, Julien; Devillers, Olivier; Glisse, Marc; Goaoc, Xavier 1 2008 Empty-ellipse graphs. Zbl 1192.52020 Devillers, Olivier; Erickson, Jeff; Goaoc, Xavier 1 2008 Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. Zbl 1302.68272 Amenta, Nina; Attali, Dominique; Devillers, Olivier 11 2007 Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. Zbl 1138.65019 Brönnimann, Hervé; Devillers, Olivier; Dujmović, Vida; Everett, Hazel; Glisse, Marc; Goaoc, Xavier; Lazard, Sylvain; Na, Hyeon-Suk; Whitesides, Sue 5 2007 Maintaining visibility information of planar point sets with a moving viewpoint. Zbl 1145.65011 Devillers, Olivier; Dujmović, Vida; Everett, Hazel; Hornus, Samuel; Whitesides, Sue; Wismath, Steve 2 2007 Lines tangent to four triangles in three-dimensional space. Zbl 1117.52007 Brönnimann, H.; Devillers, O.; Lazard, S.; Sottile, F. 1 2007 Optimal succinct representations of planar maps. Zbl 1153.68515 Aleardi, Luca Castelli; Devillers, Olivier; Schaeffer, Gilles 7 2006 Drawing \(K_n\) in three dimensions with one bend per edge. Zbl 1171.68602 Devillers, Olivier; Everett, Hazel; Lazard, Sylvain; Pentcheva, Maria; Wismath, Stephen K. 1 2006 Succinct representation of triangulations with a boundary. Zbl 1161.68396 Castelli Aleardi, L.; Devillers, Olivier; Schaeffer, Gilles 15 2005 Centroidal Voronoi diagrams for isotropic surface remeshing. Zbl 1101.68897 Alliez, Pierre; Colin de Verdiére, Éric; Devillers, Olivier; Isenburg, Martin 12 2005 The number of lines tangent to arbitrary convex polyhedra in 3D. Zbl 1374.68645 Brönnimann, H.; Devillers, O.; Dujmović, V.; Everett, H.; Glisse, M.; Goaoc, X.; Lazard, S.; Na, H.-S.; Whitesides, S. 1 2004 Inner and outer rounding of set operations on lattice polygonal regions. Zbl 1378.65054 Devillers, Olivier; Guigue, Philippe 1 2004 Chromatic variants of the Erdős–Szekeres theorem on points in convex position. Zbl 1034.52014 Devillers, Olivier; Hurtado, Ferran; Károlyi, Gyula; Seara, Carlos 21 2003 Circular cylinders through four or five points in space. Zbl 1031.52008 Devillers, Olivier; Mourrain, Bernard; Preparata, Franco P.; Trebuchet, Philippe 6 2003 Perturbations and vertex removal in a 3D Delaunay triangulation. Zbl 1094.68679 Devillers, Olivier; Teillaud, Monique 4 2003 The expected number of 3D visibility events is linear. Zbl 1041.68107 Devillers, Olivier; Dujmovic, Vida; Everett, Hazel; Goaoc, Xavier; Lazard, Sylvain; Na, Hyeon-Suk; Petitjean, Sylvain 3 2003 Minimal set of constraints for 2D constrained Delaunay reconstruction. Zbl 1093.68126 Devillers, Olivier; Estkowski, Regina; Gandoin, Pierre-Marie; Hurtado, Ferran; Ramos, Pedro; Sacristán, Vera 3 2003 Culling a set of points for roundness or cylindricity evaluations. Zbl 1074.68637 Devillers, Olivier; Preparata, Franco P. 1 2003 Triangulations in CGAL. Zbl 1016.68138 Boissonnat, Jean-Daniel; Devillers, Olivier; Pion, Sylvain; Teillaud, Monique; Yvinec, Mariette 16 2002 The Delaunay hierarchy. Zbl 1066.68138 Devillers, Olivier 12 2002 Walking in a triangulation. Zbl 1066.68139 Devillers, Olivier; Pion, Sylvain; Teillaud, Monique 11 2002 Splitting a Delaunay triangulation in linear time. Zbl 1016.68137 Chazelle, B.; Devillers, O.; Hurtado, F.; Mora, M.; Sacristan, V. 8 2002 Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Zbl 1016.68142 Devillers, Olivier; Fronville, Alexandra; Mourrain, Bernard; Teillaud, Monique 6 2002 Computing roundness is easy if the set is almost round. Zbl 1152.68664 Devillers, Olivier; Ramos, Pedro A. 3 2002 On deletion in Delaunay triangulations. Zbl 1152.68663 Devillers, Olivier 2 2002 Walking in a triangulation. Zbl 1374.68659 Devillers, Olivier; Pion, Sylvain; Teillaud, Monique 10 2001 Circular separability of polygons. Zbl 0984.68175 Boissonnat, Jean-Daniel; Czyzowicz, Jurek; Devillers, Olivier; Yvinec, Mariette 2 2001 Splitting a Delaunay triangulation in linear time. Zbl 1006.68560 Chazelle, Bernard; Devillers, Olivier; Hurtado, Ferran; Mora, Mercè; Sacristán, Vera; Teillaud, Monique 1 2001 The shuffling buffer. Zbl 1074.68636 Devillers, Olivier; Guigue, Philippe 1 2001 Computing largest circles separating two sets of segments. Zbl 1074.68631 Boissonnat, Jean-Daniel; Czyzowicz, Jurek; Devillers, Olivier; Urrutia, Jorge; Yvinec, Mariette 8 2000 Removing degeneracies by perturbing the problem or perturbing the world. Zbl 0996.65019 Alliez, Pierre; Devillers, Olivier; Snoeyink, Jack 5 2000 Algebraic methods and arithmetic filtering for exact predicates on circle arcs. Zbl 1374.68658 Devillers, Olivier; Fronville, Alexandra; Mourrain, Bernard; Teillaud, Monique 4 2000 Triangulations in CGAL (extended abstract). Zbl 1374.68643 Boissonnat, Jean-Daniel; Devillers, Olivier; Teillaud, Monique; Yvinec, Mariette 3 2000 Evaluating the cylindricity of a nominally cylindrical point set. Zbl 0953.65011 Devillers, Olivier; Preparata, Franco P. 2 2000 Further results on arithmetic filters for geometric predicates. Zbl 0944.68182 Devillers, Olivier; Preparata, Franco P. 4 1999 Optimal line bipartitions of point sets. Zbl 1026.65011 Devillers, Olivier; Katz, Matthew J. 3 1999 Finding an ordinary conic and an ordinary hyperplane. Zbl 0938.68877 Devillers, Olivier; Mukhopadhyay, Asish 1 1999 Computing the maximum overlap of two convex polygons under translations. Zbl 0910.68226 de Berg, M.; Cheong, O.; Devillers, O.; van Kreveld, M.; Teillaud, M. 13 1998 Checking the convexity of polytopes and the planarity of subdivisions. Zbl 0921.68101 Devillers, Olivier; Liotta, Giuseppe; Preparata, Franco P.; Tamassia, Roberto 11 1998 A probabilistic analysis of the power of arithmetic filters. Zbl 0912.68204 Devillers, O.; Preparata, F. P. 7 1998 Dog bites postman: Point location in the moving Voronoi diagram and related problems. Zbl 1035.68528 Devillers, Olivier; Golin, Mordecai J. 5 1998 Evaluating signs of determinants using single-precision arithmetic. Zbl 0865.68119 Avnaim, Francis; Boissonnat, Jean-Daniel; Devillers, Olivier; Preparata, Franco P.; Yvinec, Mariette 9 1997 Computing a single cell in the overlay of two simple polygons. Zbl 1336.68269 de Berg, Mark; Devillers, Olivier; Dobrindt, Katrin; Schwarzkopf, Otfried 1 1997 Queries on Voronoi diagrams on moving points. Zbl 0857.68104 Devillers, O.; Golin, M.; Kedem, K.; Schirra, S. 7 1996 An algorithm for constructing the convex hull of a set of spheres in dimension \(d\). Zbl 0849.68125 Boissonnat, Jean-Daniel; Cérézo, André; Devillers, Olivier; Duquesne, Jacqueline; Yvinec, Mariette 6 1996 An introduction to randomization in computational geometry. Zbl 0871.68166 Devillers, Olivier 1 1996 Scalable algorithms for bichromatic line segment intersection problems on coarse grained multicomputers. Zbl 0871.68178 Fabri, Andreas; Devillers, Olivier 1 1996 Optimal line bipartitions of point sets. Zbl 1512.68412 Devillers, Olivier; Katz, Matthew J. 1 1996 Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Zbl 0875.68901 Devillers, Olivier; Golin, Mordecai J. 5 1995 A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Zbl 0780.68109 Boissonnat, Jean-Daniel; Devillers, Olivier; Teillaud, Monique 10 1993 Applications of random sampling to on-line algorithms in computational geometry. Zbl 0769.68118 Boissonnat, Jean-Daniel; Devillers, Olivier; Schott, René; Teillaud, Monique; Yvinec, Mariette 28 1992 Randomization yields simple \(O(n\log{}^*n)\) algorithms for difficult \({\Omega{}}(n)\) problems. Zbl 0761.68094 Devillers, Olivier 15 1992 Fully dynamic Delaunay triangulation in logarithmic expected per operation. Zbl 0773.68066 Devillers, Olivier; Meiser, Stefan; Teillaud, Monique 10 1992 Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Zbl 0765.68204 Devillers, Olivier; Meiser, Stefan; Teillaud, Monique 3 1991 Computing the union of 3-colored triangles. Zbl 0735.68083 Boissonnat, Jean-Daniel; Devillers, Olivier; Preparata, Franco P. 2 1991 all cited Publications top 5 cited Publications all top 5 Cited by 632 Authors 31 Devillers, Olivier 15 Urrutia Galicia, Jorge L. 10 Bose, Prosenjit K. 9 Boissonnat, Jean-Daniel 9 Lazard, Sylvain 9 Mehlhorn, Kurt 9 Teillaud, Monique 8 Cheong, Otfried 6 Ahn, Hee-Kap 6 de Berg, Mark Theodoor 6 Fabila-Monroy, Ruy 6 He, Meng 6 Papadopoulou, Evanthia 5 Castelli Aleardi, Luca 5 Glisse, Marc 5 Hurtado, Ferran 5 Liu, Chih-Hung 5 Löffler, Maarten 5 Munro, J. Ian 5 Pion, Sylvain 5 Seara, Carlos 4 Aichholzer, Oswin 4 Biniaz, Ahmad 4 Bonichon, Nicolas 4 Chakraborty, Sankardeep 4 de Carufel, Jean-Lou 4 Everett, Hazel 4 Langerman, Stefan 4 Morin, Pat 4 Mulzer, Wolfgang Johann Heinrich 4 Sakai, Toshinori 4 Seidel, Raimund 4 Smid, Michiel H. M. 4 Snoeyink, Jack Scott 4 Vigneron, Antoine 3 Bewley, Thomas R. 3 Beyhaghi, Pooriya 3 Bohler, Cecilia 3 Buchin, Kevin 3 Cardinal, Jean 3 Dobrindt, Katrin T. G. 3 Efrat, Alon 3 Emiris, Ioannis Z. 3 Farzan, Arash 3 Fisikopoulos, Vissarion 3 Fuentes-Sepúlveda, José 3 Goaoc, Xavier 3 Golin, Mordecai J. 3 Goodrich, Michael Truman 3 Halperin, Dan 3 Huemer, Clemens 3 Kim, Deok-Soo 3 Klein, Rolf-Dieter 3 Lenhart, William J. 3 Lingas, Andrzej 3 Maheshwari, Anil 3 Meiser, Stefan 3 Millman, David L. 3 Sadakane, Kunihiko 3 Satti, Srinivasa Rao 3 Sharir, Micha 3 Shin, Chan-Su 3 Thäle, Christoph 3 Tsiotras, Panagiotis 3 van Kreveld, Marc J. 3 Yamanaka, Katsuhisa 3 Yap, Chee-Keng 3 Yvinec, Mariette 3 Zhang, Linqiao 2 Abrahamsen, Mikkel 2 Abu-Affash, A. Karim 2 Acan, Hüseyin 2 Akitaya, Hugo A. 2 Alegría, Carlos 2 Allmaras, Steven R. 2 Alt, Helmut 2 Amenta, Nina 2 Bakolas, Efstathios 2 Bárány, Imre 2 Barbay, Jérémy 2 Bereg, Sergey N. 2 Berman, Piotr 2 Bhore, Sujoy Kumar 2 Bonnet, Gilles 2 Bousquet-Mélou, Mireille 2 Brass, Peter 2 Calka, Pierre 2 Caraballo, Luis-Evaristo 2 Carmi, Paz 2 Chazelle, Bernard 2 Chenavier, Nicolas 2 Cheng, Siu-Wing 2 Clarkson, Kenneth L. 2 Cook, Atlas F. IV 2 Darmofal, David L. 2 De Castro, Pedro Machado Manhães 2 De Loera, Jesús A. 2 Dujmović, Vida 2 Dutta, Kunal 2 Eppstein, David Arthur ...and 532 more Authors all top 5 Cited in 85 Serials 58 Computational Geometry 30 Discrete & Computational Geometry 25 International Journal of Computational Geometry & Applications 22 Algorithmica 9 Theoretical Computer Science 8 Information Processing Letters 8 Journal of Computational Physics 8 Graphs and Combinatorics 7 Discrete Applied Mathematics 7 Computer Aided Geometric Design 5 Journal of Global Optimization 4 Automatica 3 Computers & Mathematics with Applications 3 ACM Transactions on Mathematical Software 3 International Journal for Numerical Methods in Engineering 3 Journal of Computational and Applied Mathematics 3 European Journal of Combinatorics 3 Journal of Discrete Algorithms 2 Computer Methods in Applied Mechanics and Engineering 2 Journal of Computer and System Sciences 2 Information and Computation 2 SIAM Journal on Discrete Mathematics 2 The Annals of Applied Probability 2 International Journal of Foundations of Computer Science 2 Applicable Algebra in Engineering, Communication and Computing 2 Journal of Mathematical Imaging and Vision 2 Computational and Applied Mathematics 2 Bernoulli 2 Journal of Combinatorial Optimization 2 Computational Geosciences 2 Mathematics in Computer Science 1 Advances in Applied Probability 1 Communications in Mathematical Physics 1 Computer Physics Communications 1 Discrete Mathematics 1 International Journal for Numerical Methods in Fluids 1 Journal of Mathematical Analysis and Applications 1 Mathematical Notes 1 Mathematical Proceedings of the Cambridge Philosophical Society 1 Moscow University Mathematics Bulletin 1 Physica A 1 Bulletin of Mathematical Biology 1 Advances in Mathematics 1 Applied Mathematics and Computation 1 BIT 1 Geometriae Dedicata 1 Information Sciences 1 Journal of the American Statistical Association 1 Journal of Combinatorial Theory. Series A 1 Journal of Geometry 1 Journal of Optimization Theory and Applications 1 Journal of Statistical Planning and Inference 1 Proceedings of the American Mathematical Society 1 SIAM Journal on Computing 1 SIAM Journal on Numerical Analysis 1 Transactions of the American Mathematical Society 1 Combinatorica 1 Applied Numerical Mathematics 1 Order 1 Journal of Symbolic Computation 1 Probability Theory and Related Fields 1 Computational Mechanics 1 Journal of Economic Dynamics & Control 1 Random Structures & Algorithms 1 Computational Mathematics and Mathematical Physics 1 Applied Mathematical Modelling 1 SIAM Journal on Applied Mathematics 1 Bulletin of the American Mathematical Society. New Series 1 Advances in Engineering Software 1 Advances in Applied Clifford Algebras 1 Engineering Analysis with Boundary Elements 1 Theory of Computing Systems 1 Vietnam Journal of Mathematics 1 Journal of Graph Algorithms and Applications 1 Interdisciplinary Information Sciences (IIS) 1 Optimization and Engineering 1 The Journal of Logic and Algebraic Programming 1 Mathematical Biosciences and Engineering 1 The European Physical Journal C. Particles and Fields 1 Journal of Zhejiang University. Science A 1 Inverse Problems and Imaging 1 Discrete Mathematics, Algorithms and Applications 1 Statistics and Computing 1 Computer Science Review 1 Annales Henri Lebesgue all top 5 Cited in 32 Fields 188 Computer science (68-XX) 90 Numerical analysis (65-XX) 75 Convex and discrete geometry (52-XX) 49 Combinatorics (05-XX) 23 Operations research, mathematical programming (90-XX) 15 Probability theory and stochastic processes (60-XX) 10 Geometry (51-XX) 5 Statistics (62-XX) 4 Partial differential equations (35-XX) 4 Algebraic topology (55-XX) 4 Mechanics of deformable solids (74-XX) 4 Fluid mechanics (76-XX) 4 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Algebraic geometry (14-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 3 Manifolds and cell complexes (57-XX) 3 Biology and other natural sciences (92-XX) 2 Commutative algebra (13-XX) 2 Differential geometry (53-XX) 2 Systems theory; control (93-XX) 2 Information and communication theory, circuits (94-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Measure and integration (28-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Approximations and expansions (41-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Quantum theory (81-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Astronomy and astrophysics (85-XX) 1 Geophysics (86-XX) Citations by Year