On the Size of the 3D Visibility Skeleton: Experimental Results (2009)
Linqiao Zhang, Hazel Everett, Sylvain Lazard, Christophe Weibel, Sue Whitesides
Abstract. The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for k convex polytopes with...
Olivier Devillers, Marc Glisse, Sylvain Lazard
for line transversals to lines and line segments
A CGAL-based Univariate Algebraic Kernel and Application to Arrangements (2009)
Sylvain Lazard, Luis Peñar, A Elias Tsigaridas
Solving univariate polynomials and multivariate polynomial systems is critical in geometric computing with curved objects. Moreover, the real roots need to be computed in a certified way in order to...
On the Topology of Planar Algebraic Curves (2009)
Jinsan Cheng, Sylvain Lazard, Luis Peñar, Marc Pouget, Fabrice Rouillier, Elias Tsigaridas
We introduce a method to compute the topology of planar algebraic curves. The curve may not be in generic position and may have vertical asymptotes. The algebraic tools are rational univariate...
The Voronoi diagram of three arbitrary lines in R 3 (2009)
Hazel Everett, Christian Gillot, Daniel Lazard, Sylvain Lazard, Marc Pouget
In this paper we study the Voronoi diagram of lines in R 3. The Voronoi diagram of three lines in general position was studied in [14]. In this paper we complete this work by presenting a complete...
The`me 3-- Interaction homme-machine, (2009)
Hafsa Deddi, Hazel Everett, Sylvain Lazard, Hafsa Deddi, Hazel Everett, Sylvain Lazard, ...
images, donne'es, connaissances
Common tangents to spheres in R 3 (2009)
Ciprian Borcea, Xavier Goaoc, Sylvain Lazard, Sylvain Petitjean, Loria Inria Lorraine
Abstract. We prove that four spheres in R 3 have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent. 1
Jean-daniel Boissonnat, Subir Kumar Ghosh, Sylvain Lazard
A linear time algorithm for computing a convex path of bounded curvature in a simple polygon
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus
ABSTRACT. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME (2009)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
Univariate Algebraic Kernel and Application to Arrangements (2009)
Lazard, Sylvain, Peñaranda, Luis, Tsigaridas, Elias P.
Solving polynomials and performing operations with real algebraic numbers are critical issues in geometric computing, in particular when dealing with curved objects. Moreover, the real roots need to...
Univariate Algebraic Kernel and Application to Arrangements (2009)
Lazard, Sylvain, Peñaranda, Luis, Tsigaridas, Elias P.
Solving polynomials and performing operations with real algebraic numbers are critical issues in geometric computing, in particular when dealing with curved objects. Moreover, the real roots need to...
The Voronoi diagram of three arbitrary lines in R3 (2009)
Everett, Hazel, Gillot, Christian, Lazard, Daniel, Lazard, Sylvain, Pouget, Marc
In this paper we study the Voronoi diagram of lines in R3 . The Voronoi diagram of three lines in general position was studied in [8]. In this paper we complete this work by presenting a complete...
The Voronoi diagram of three arbitrary lines in R3 (2009)
Everett, Hazel, Gillot, Christian, Lazard, Daniel, Lazard, Sylvain, Pouget, Marc
In this paper we study the Voronoi diagram of lines in R3 . The Voronoi diagram of three lines in general position was studied in [8]. In this paper we complete this work by presenting a complete...
On the Degree of Standard Geometric Predicates for Line Transversals in 3D (2009)
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Zhang, Linqiao
In this paper we study various geometric predicates for determining the existence of and categorizing the configurations of lines in 3D that are transversal to lines or segments. We compute the...
On the Complexity of Umbra and Penumbra (2009)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
On the topology of planar algebraic curves (2009)
Cheng, Jinsan, Lazard, Sylvain, Peñaranda, Luis Mariano, Pouget, Marc, Rouillier, Fabrice, Tsigaridas, Elias P.
We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and...
On the Degree of Standard Geometric Predicates for Line Transversals in 3D (2009)
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Zhang, Linqiao
In this paper we study various geometric predicates for determining the existence of and categorizing the configurations of lines in 3D that are transversal to lines or segments. We compute the...
On the Complexity of Umbra and Penumbra (2009)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Univariate Algebraic Kernel and Application to Arrangements (2009)
Lazard, Sylvain, Mariano Penaranda, Luis, Tsigaridas, Elias P.
Abstract. We present a cgal-based univariate algebraic kernel, which provides certi
The Voronoi diagram of three lines (2009)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
On the topology of planar algebraic curves (2009)
Cheng, Jinsan, Lazard, Sylvain, Peñaranda, Luis Mariano, Pouget, Marc, Rouillier, Fabrice, Tsigaridas, Elias P.
We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and...
Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices (2009)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that...
Univariate Algebraic Kernel and Application to Arrangements (2009)
Lazard, Sylvain, Mariano Penaranda, Luis, Tsigaridas, Elias P.
Abstract. We present a cgal-based univariate algebraic kernel, which provides certi
The Voronoi diagram of three lines (2009)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices (2009)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that...
Problèmes de Géométrie Algorithmique sur les Droites et les Quadriques en Trois Dimensions (2008)
Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une part sur le développement d'algorithmes géométriques certifiés et efficaces traitant...
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices ⋆ (2008)
Hazel Everett, Sylvain Lazard, Stephen Wismath, Inria Lorraine
Abstract. This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is...
ABSTRACT Intersecting Quadrics: An Efficient and Exact Implementation (2008)
Sylvain Lazard, Loria-inria Lorraine
We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based...
Chapter 1 TOWARDS THE ROBUST INTERSECTION OF IMPLICIT QUADRICS (2008)
Laurent Dupont, Sylvain Lazard, Sylvain Petitjean, Daniel Lazard
Abstract We are interested in efficiently and robustly computing a parametric form of the intersection of two implicit quadrics with rational coefficients. Our method is similar in spirit to the...
Between umbra and penumbra (2008)
Julien Demouth, Olivier Devillers, Hazel Everett, Sylvain Lazard, Raimund Seidel
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Stephen
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Near-Optimal Parameterization of the Intersection of Quadrics: I.~The Generic Algorithm (2008)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present an exact and efficient algorithm for computing a proper parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present here the first classification of pencils of quadrics based on the type of their intersection in real projective space and we show how this classification can be used to compute efficiently...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We conclude, in this third part, the presentation of an algorithm for computing an exact and proper parameterization of the intersection of two quadrics. The coordinate functions of the...
Near-Optimal Parameterization of the Intersection of Quadrics: I.~The Generic Algorithm (2008)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present an exact and efficient algorithm for computing a proper parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present here the first classification of pencils of quadrics based on the type of their intersection in real projective space and we show how this classification can be used to compute efficiently...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We conclude, in this third part, the presentation of an algorithm for computing an exact and proper parameterization of the intersection of two quadrics. The coordinate functions of the...
Universal Sets of $n$ Points for 1-bend Drawings of Planar Graphs with $n$ Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Universal Sets of $n$ Points for 1-bend Drawings of Planar Graphs with $n$ Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Steve
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
On The Topology of Planar Algebraic Curves (2008)
Cheng, Jinsan, Lazard, Sylvain, Peñaranda, Luis Mariano, Pouget, Marc, Rouillier, Fabrice, Tsigaridas, Elias P.
We introduce a method to compute the topology of planar algebraic curves. The curve may not be in generic position and may have vertical asymptotes. The algebraic tools are rational univariate...
On The Topology of Planar Algebraic Curves (2008)
Cheng, Jinsan, Lazard, Sylvain, Peñaranda, Luis Mariano, Pouget, Marc, Rouillier, Fabrice, Tsigaridas, Elias P.
We introduce a method to compute the topology of planar algebraic curves. The curve may not be in generic position and may have vertical asymptotes. The algebraic tools are rational univariate...
Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices (2008)
Everett, Hazel, Lazard, Sylvain, Liotta, Giuseppe, Wismath, Stephen
This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that...
Predicates for line transversals to lines and line segments in three-dimensional space (2008)
Devillers, Olivier, Glisse, Marc, Lazard, Sylvain
When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are...
Predicates for line transversals to lines and line segments in three-dimensional space (2008)
Devillers, Olivier, Glisse, Marc, Lazard, Sylvain
When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without...
Walking Your Dog in the Woods in Polynomial Time (2008)
Wolf Chambers, Erin, Colin De Verdire, Eric, Erickson, Jeff, Lazard, Sylvain, Lazarus, Francis, Thite, Shripad
The Frechet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without...
On the Size of the 3D Visibility Skeleton: Experimental Results (2008)
Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Weibel, Christophe, Whitesides, Sue
The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for $k$ convex polytopes with $n$...
An Upper Bound on the Average Size of Silhouettes (2008)
It is a widely observed phenomenon in computer graphics that the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. This paper provides, for the first time,...
A CGAL-based Univariate Algebraic Kernel and Application to Arrangements (2008)
Lazard, Sylvain, Mariano Penaranda, Luis, Tsigaridas, Elias P.
Solving univariate polynomials and operations with real algebraic numbers are critical in geometric computing with curved objects. Moreover, the real roots need to be computed in a certified way in...
On the Size of the 3D Visibility Skeleton: Experimental Results (2008)
Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Weibel, Christophe, Whitesides, Sue
The 3D visibility skeleton is a data structure used to encode global visibility information about a set of objects. Previous theoretical results have shown that for $k$ convex polytopes with $n$...
An Upper Bound on the Average Size of Silhouettes (2008)
It is a widely observed phenomenon in computer graphics that the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. This paper provides, for the first time,...
A CGAL-based Univariate Algebraic Kernel and Application to Arrangements (2008)
Lazard, Sylvain, Mariano Penaranda, Luis, Tsigaridas, Elias P.
Solving univariate polynomials and operations with real algebraic numbers are critical in geometric computing with curved objects. Moreover, the real roots need to be computed in a certified way in...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2008)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
On the degree of standard geometric predicates for line transversals (2008)
Hazel Everett, Sylvain Lazard, William Lenhart, Jeremy Redburn, Linqiao Zhang
In this paper we study various geometric predicates for determining the existence of and categorizing the configurations of lines in 3D that are transversal to lines or segments. We compute the...
On the topology of planar algebraic curves (2008)
Jinsan Cheng, Sylvain Lazard, Luis Peñar, Marc Pouget, Fabrice Rouillier, Elias Tsigaridas
We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and...
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Shortest Paths of Bounded Curvature in a Convex Polygon (2007)
Sylvain Lazard, T. Biedl (rutgers, Now At Mcgill, H. Everett (uqam
f bounded curvature between any two configurations. Furthermore, such a path is (see Figure 1) either of type CCC (i.e., the concatenation of three circular arcs of unit radius), or of type CSC...
Olivier Devillers, Vida Dujmovi C, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-suk Na, ...
A linear bound on the expected
de recherche Motion Planning of Legged Robots (2007)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, Sylvain Lazard, Sylvain Lazard, ...
Abstract: We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The...
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss
Abstract. This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone...
Jean-daniel Boissonnat, Sylvain Lazard
polynomial-time algorithm for computing a shortest path of
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Sylvain Lazard, Sylvain Lazard
apport de recherche
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
Whitesides d a
Jean-daniel Boissonnat, Sylvain Lazard
A polynomial-time algorithm for computing a shortest path of
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Olivier Devillers, Olivier Devillers, Sylvain Lazard, Sylvain Lazard
apport de recherche
On the theoretical complexity of the silhouette of a polyhedron Mémoire soutenu le vendredi 5 septembre 2003 par
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Sylvain Lazard, Sylvain Lazard
apport de recherche
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
An Upper Bound on the Average Size of Silhouettes (2007)
It is a widely observed phenomenon in computer graphics that the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. This paper provides, for the first time,...
Lines tangent to four triangles in three-dimensional space (2007)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Lines tangent to four triangles in three-dimensional space (2007)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Une borne supérieure sur la taille moyenne des silhouettes (2007)
Il est connu en infographie que la taille de la silhouette d'un polyèdre s'avère souvent, en pratique, bien plus petite que la taille du polyèdre entier. Cet article est le premier à fournir des...
Une borne supérieure sur la taille moyenne des silhouettes (2007)
Il est connu en infographie que la taille de la silhouette d'un polyèdre s'avère souvent, en pratique, bien plus petite que la taille du polyèdre entier. Cet article est le premier à fournir des...
Il est connu en infographie que la taille de la silhouette d'un polyèdre s'avère souvent, en pratique, bien plus petite que la taille du polyèdre entier. Cet article est le premier à fournir des...
Il est connu en infographie que la taille de la silhouette d'un polyèdre s'avère souvent, en pratique, bien plus petite que la taille du polyèdre entier. Cet article est le premier à fournir des...
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram, in $\R^3$, of three lines in general position, that is, that are pairwise skew and not all parallel to a common plane. In particular, we show...
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram of three lines in $\R^3$. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that...
The Voronoi Diagram of Three Lines (2007)
Everett, Hazel, Lazard, Daniel, Lazard, Sylvain, Safey El Din, Mohab
We give a complete description of the Voronoi diagram of three lines in $\R^3$. In particular, we show that the topology of the Voronoi diagram is invariant for three lines in general position, that...
On the Complexity of Umbra and Penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
On the Complexity of Umbra and Penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Between umbra and penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Between umbra and penumbra (2007)
Demouth, Julien, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Lazard, Sylvain, Seidel, Raimund
Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light source; it is in full light if it sees...
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)
Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...
Farthest-Polygon Voronoi Diagrams (2007)
Cheong, Otfried, Everett, Hazel, Glisse, Marc, Gudmundsson, Joachim, Hornus, Samuel, Lazard, Sylvain, ...
Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest...
On the Expected Size of the 2D Visibility Complex (2007)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the asymptotic expected number of free bitangents (which correspond to 0-faces of...
Lines and free line segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2007)
Bronnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the set of...
Farthest-Polygon Voronoi Diagrams (2007)
Cheong, Otfried, Everett, Hazel, Glisse, Marc, Gudmundsson, Joachim, Hornus, Samuel, Lazard, Sylvain, ...
Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest...
On the Expected Size of the 2D Visibility Complex (2007)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the asymptotic expected number of free bitangents (which correspond to 0-faces of...
Problèmes de Géométrie Algorithmique sur les Droites et les Quadriques en Trois Dimensions (2007)
Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une part sur le développement d'algorithmes géométriques certifiés et efficaces traitant...
Problèmes de Géométrie Algorithmique sur les Droites et les Quadriques en Trois Dimensions (2007)
Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une part sur le développement d'algorithmes géométriques certifiés et efficaces traitant...
Problèmes de Géométrie Algorithmique sur les Droites et les Quadriques en Trois Dimensions (2007)
Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une part sur le développement d'algorithmes géométriques certifiés et efficaces traitant...
Towards an Implementation of the 3D Visibility Skeleton (2007)
Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Whitesides, Sue
In this note we describe the contents of a video illustrating an algorithm for computing the 3D visibility skeleton of a set of disjoint convex polytopes.
Towards an Implementation of the 3D Visibility Skeleton (2007)
Zhang, Linqiao, Everett, Hazel, Lazard, Sylvain, Whitesides, Sue
In this note we describe the contents of a video illustrating an algorithm for computing the 3D visibility skeleton of a set of disjoint convex polytopes.
Farthest-Polygon Voronoi Diagrams ∗ (2007)
Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, ...
Given a family of k disjoint connected polygonal sites of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest...
WALKING YOUR DOG IN THE WOODS IN POLYNOMIAL TIME 1 (2007)
Erin Wolf Chambers, Éric Colin, De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, ...
Abstract. The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other,...
Parabola Separation Queries and their Application to Stone Throwing (2007)
Cheong, Otfried, Everett, Hazel, Kim, Hyo-Sil, Lazard, Sylvain, Schott, Rene
Given two sets A and B of m non-crossing line segments in the plane, we show how to compute in O(m log m) time a data structure that uses O(m) storage and supports the following query in O(log m)...
On the Expected Size of the 2D Visibility Complex (2006)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the expected asymptotic number of free bitangents (which correspond to the 0-faces...
Drawing K_n in Three Dimensions with One Bend per Edge (2006)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....
Drawing K_n in Three Dimensions with One Bend per Edge (2006)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....
Intersecting Quadrics: An Efficient and Exact Implementation (2006)
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
On the Expected Size of the 2D Visibility Complex (2006)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the expected asymptotic number of free bitangents (which correspond to the 0-faces...
Predicates for Line Transversals in 3D (2006)
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Redburn, Jeremy, Zhang, Linqiao
In this paper we study various predicates concerning line transversals to lines and segments in 3D. We compute the degrees of standard methods of evaluating these predicates. The degrees of some of...
Predicates for Line Transversals in 3D (2006)
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Redburn, Jeremy, Zhang, Linqiao
In this paper we study various predicates concerning line transversals to lines and segments in 3D. We compute the degrees of standard methods of evaluating these predicates. The degrees of some of...
Predicates for Line Transversals in 3D (2006)
Everett, Hazel, Lazard, Sylvain, Lenhart, Bill, Redburn, Jeremy, Zhang, Linqiao
In this paper we study various predicates concerning line transversals to lines and segments in 3D. We compute the degrees of standard methods of evaluating these predicates. The degrees of some of...
On the Expected Size of the 2D Visibility Complex (2006)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the expected asymptotic number of free bitangents (which correspond to the 0-faces...
Intersecting Quadrics: An Efficient and Exact Implementation (2006)
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
Common Tangents to Spheres in $R3$ (2006)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We prove that four spheres in $R3$ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2006)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Steve
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by~$O(n^{2.5})$.
Common Tangents to Spheres in $R3$ (2006)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We prove that four spheres in $R3$ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2006)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Steve
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by~$O(n^{2.5})$.
Drawing K_n in Three Dimensions with One Bend per Edge (2006)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of K_n in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n^{2.5})....
Otfried Cheong, Hazel Everett, Hyo-sil Kim, Sylvain Lazard, René Schott
Abstract. Given two sets A and B of m non-intersecting line segments in the plane, we show how to compute in O(m log m) time a data structure that uses O(m) space and allows to answer the following...
Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)
Olivier Devillers, Vida Dujmović, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, ...
SUE WHITESIDES∗ ∗ Abstract. Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional...
Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra (2006)
Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Xavier Goaoc, Sylvain Lazard, ...
Abstract. Motivated by visibility problems in three dimensions, we investigate the complexity and construction of the set of tangent lines in a scene of three-dimensional polyhedra. We prove that the...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, robust, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
In Part II [3] of this paper, we have shown, using a classification of pencils of quadrics over the reals, how to determine quickly and efficiently the real type of the intersection of two given...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
While Part I [2] of this paper was devoted mainly to quadrics intersecting in a smooth quartic, we now focus on singular intersections. To produce optimal or near-optimal parameterizations in all...
Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm (2005)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational...
Drawing Kn in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, robust, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
In Part II [3] of this paper, we have shown, using a classification of pencils of quadrics over the reals, how to determine quickly and efficiently the real type of the intersection of two given...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
While Part I [2] of this paper was devoted mainly to quadrics intersecting in a smooth quartic, we now focus on singular intersections. To produce optimal or near-optimal parameterizations in all...
Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm (2005)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational...
Drawing Kn in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm (2005)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
While Part I [2] of this paper was devoted mainly to quadrics intersecting in a smooth quartic, we now focus on singular intersections. To produce optimal or near-optimal parameterizations in all...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
In Part II [3] of this paper, we have shown, using a classification of pencils of quadrics over the reals, how to determine quickly and efficiently the real type of the intersection of two given...
Brönnimann, Hervé, Devillers, Olivier, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.
Lazard, Sylvain, Peñaranda, Luis Mariano, Petitjean, Sylvain
We present the first complete, robust, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
An Experimental Assessment of the 2D Visibility Complex (2005)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We make an experimental assessment of the size of the 2D visibility complex of disjoint unit discs randomly distributed in the plane with density $\mu$. We observe that the number of free bitangents...
Intersecting Quadrics: An Efficient and Exact Implementation (2005)
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
Line tangents to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in R^3. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and at most 156...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in $\mathbb{R}^3$. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of tangents, and...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.
An Experimental Assessment of the 2D Visibility Complex (2005)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We make an experimental assessment of the size of the 2D visibility complex of disjoint unit discs randomly distributed in the plane with density $\mu$. We observe that the number of free bitangents...
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.
Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm (2005)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
While Part I [2] of this paper was devoted mainly to quadrics intersecting in a smooth quartic, we now focus on singular intersections. To produce optimal or near-optimal parameterizations in all...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
In Part II [3] of this paper, we have shown, using a classification of pencils of quadrics over the reals, how to determine quickly and efficiently the real type of the intersection of two given...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.
Lazard, Sylvain, Peñaranda, Luis Mariano, Petitjean, Sylvain
We present the first complete, robust, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm (2005)
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
While Part I [2] of this paper was devoted mainly to quadrics intersecting in a smooth quartic, we now focus on singular intersections. To produce optimal or near-optimal parameterizations in all...
Dupont, Laurent, Lazard, Daniel, Lazard, Sylvain, Petitjean, Sylvain
In Part II [3] of this paper, we have shown, using a classification of pencils of quadrics over the reals, how to determine quickly and efficiently the real type of the intersection of two given...
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each...
Lines tangent to four triangles in three-dimensional space (2005)
Brönnimann, Hervé, Devillers, Olivier, Lazard, Sylvain, Sottile, Frank
We investigate the lines tangent to four triangles in three-dimensional space. By a construction, there can be as many as 62 tangents. We show that there are at most 162 connected components of...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^2.5)$.
Lazard, Sylvain, Peñaranda, Luis Mariano, Petitjean, Sylvain
We present the first complete, robust, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
An Experimental Assessment of the 2D Visibility Complex (2005)
Everett, Hazel, Lazard, Sylvain, Petitjean, Sylvain, Zhang, Linqiao
We make an experimental assessment of the size of the 2D visibility complex of disjoint unit discs randomly distributed in the plane with density $\mu$. We observe that the number of free bitangents...
Transversals to line segments in three-dimensional space (2005)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of $n$ line segments in $\mathbb{R}^3$. Generically, the set of transversal to four segments consist...
Drawing $K_n$ in Three Dimensions with One Bend per Edge (2005)
Devillers, Olivier, Everett, Hazel, Lazard, Sylvain, Pentcheva, Maria, Wismath, Stephen
We give a drawing of $K_n$ in 3D in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.
On the expected size of the 2d visibility complex (2005)
Hazel Everett, Sylvain Lazard, Sylvain Petitjean, Linqiao Zhang
We study the expected size of the 2D visibility complex of randomly distributed objects in the plane. We prove that the asymptotic expected number of free bitangents (which correspond to 0-faces of...
An experimental assessment of the 2d visibility complex (2005)
Hazel Everett, Sylvain Lazard, Sylvain Petitjean, Linqiao Zhang
We make an experimental assessment of the size of the 2D visibility complex of disjoint unit discs randomly distributed in the plane with density µ. We observe that the number of free bitangents is...
Article Type Communicated by Submitted Revised (2005)
Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, Inria Lorraine, ...
We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n 2.5).
Article Type Communicated by Submitted Revised (2005)
Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, Inria Lorraine, ...
We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by O(n 2.5).
Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean, Thème Sym, Laurent Dupont, ...
apport de recherche
Laurent Dupont, Sylvain Lazard, Daniel Lazard, Sylvain Petitjean
� � � � � � � � � � � � � � �Æ � � � � Categories and Subject Descriptors General Terms
Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean, Thème Sym, Laurent Dupont, ...
apport de recherche
Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean, Thème Sym, Laurent Dupont, ...
apport de recherche
Common Tangents to Spheres in R^3 (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We prove that four spheres in $\R^3$ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.
On tangents to quadric surfaces (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We study the variety of common tangents for up to four quadric surfaces in projective three-space, with particular regard to configurations of four quadrics admitting a continuum of common tangents....
Common Tangents to Spheres in R^3 (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We prove that four spheres in $\R^3$ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.
Common Tangents to Spheres in R^3 (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We prove that four spheres in $\R^3$ have infinitely many real common tangents if and only if they have aligned centers and at least one real common tangent.
Intersecting Quadrics: An Efficient and Exact Implementation (2004)
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based...
Intersecting Quadrics: An Efficient and Exact Implementation (2004)
Lazard, Sylvain, Mariano Penaranda, Luis, Petitjean, Sylvain
We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
Orientation des pièces artistiques pour le procédé de Stratoconception (2004)
Lauvaux, Geoffroy, Lazard, Sylvain, Barlier, Claude
Si l'orientation des pièces lors de leur réalisation est un paramètre commun à tous les procédés de prototypage rapide, son choix repose sur une multitude de critères variant selon le...
The Number of Lines Tangent to Arbitrary Convex Polyhedra in 3D (2004)
Brönnimann, Hervé, Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Glisse, Marc, Goaoc, Xavier, ...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a...
Orientation des pièces artistiques pour le procédé de Stratoconception (2004)
Lauvaux, Geoffroy, Lazard, Sylvain, Barlier, Claude
Si l'orientation des pièces lors de leur réalisation est un paramètre commun à tous les procédés de prototypage rapide, son choix repose sur une multitude de critères variant selon le...
Intersecting quadrics: An efficient and exact implementation (2004)
Sylvain Lazard, Luis Mariano Pear, A Sylvain Petitjean
We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based...
Intersecting Quadrics: An Efficient and Exact Implementation (2004)
Sylvain Lazard, Loria-inria Lorraine, Luis Mariano Penaranda, Sylvain Petitjean
We present the first complete, exact and e#cient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coe#cients of arbitrary size. It is based on...
Intersecting quadrics: An efficient and exact implementation (2004)
Sylvain Lazard, Luis Mariano Peñar, A Sylvain Petitjean
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
S.: Intersecting quadrics : An efficient and exact implementation (2004)
Sylvain Lazard, Luis Mariano Peñar, A Sylvain Petitjean
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the...
On Tangents to Quadric Surfaces (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We study the variety of common tangents for up to four quadric surfaces in projective three-space, with particular regard to congurations of four quadrics admitting a continuum of common tangents. We...
On Tangents to Quadric Surfaces (2004)
Borcea, Ciprian, Goaoc, Xavier, Lazard, Sylvain, Petitjean, Sylvain
We study the variety of common tangents for up to four quadric surfaces in projective three-space, with particular regard to congurations of four quadrics admitting a continuum of common tangents. We...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
The number of transversals to line segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n>2 arbitrary line segments in R^3 admit 0, 1, ..., n or...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
Transversals to Line Segments in R^3 (2003)
Brönnimann, Hervé, Everett, Hazel, Lazard, Sylvain, Sottile, Frank, Whitesides, Sue
We completely describe the structure of the connected components of transversals to a collection of n line segments in R^3. We show that n3 arbitrary line segments in R^3 admit 0, 1, , n or...
The expected number of 3D visibility events is linear (2003)
Th Emes Et, Vida Dujmovic, Sylvain Lazard, Olivier Devillers, Olivier Devillers, ...
apport de recherche
Near-Optimal Parameterization of the Intersection of Quadrics (2003)
Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean
In this paper, we present the rst exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics whose coecients are rational. Combining...
Near-Optimal Parameterization of the Intersection of Quadrics (2003)
Laurent Dupont, Daniel Lazard, Sylvain Lazard
In this paper, we present the first exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics whose coe#cients are rational. Combining...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
The expected number of 3D visibility events is linear (2002)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Goaoc, Xavier, Lazard, Sylvain, Na, Hyeon-Suk, ...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the...
Interpolation with Curvature Constraints (2002)
Deddi, Hafsa, Everett, Hazel, Lazard, Sylvain
We address the problem of controlling the curvature of a Bezier curve interpolating a given set of data. More precisely, given two points M and N, two directions u(right arrow) and upsilon(right...
Towards The Robust Intersection Of Implicit Quadrics (2001)
Laurent Dupont, Sylvain Lazard, Sylvain Petitjean, Daniel Lazard
We are interested in eciently and robustly computing a parametric form of the intersection of two implicit quadrics with rational coe- cients. Our method is similar in spirit to the general method...
Curvature-Constrained Shortest Paths in a Convex Polygon (2000)
Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue
Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...
Interpolation with Curvature Constraints (2000)
Deddi, Hafsa, Everett, Hazel, Lazard, Sylvain
We address the problem of controlling the curvature of a B{ézier curve interpolating a given set of data. More precisely, given two points $M$ and $N$, two directions $\vecu$ and $\vecv$, and a...
Curvature-Constrained Shortest Paths in a Convex Polygon (2000)
Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue
Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...
Interpolation with Curvature Constraints (2000)
Deddi, Hafsa, Everett, Hazel, Lazard, Sylvain
We address the problem of controlling the curvature of a B{ézier curve interpolating a given set of data. More precisely, given two points $M$ and $N$, two directions $\vecu$ and $\vecv$, and a...
Curvature-Constrained Shortest Paths in a Convex Polygon (2000)
Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue
Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...
Interpolation with Curvature Constraints (2000)
Deddi, Hafsa, Everett, Hazel, Lazard, Sylvain
We address the problem of controlling the curvature of a B{ézier curve interpolating a given set of data. More precisely, given two points $M$ and $N$, two directions $\vecu$ and $\vecv$, and a...
Motion Planning of Legged Robots (2000)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Motion Planning of Legged Robots (2000)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Motion planning of legged robots (2000)
Jean-daniel Boissonnat, Olivier Devillers, Sylvain Lazard
Abstract. We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The...
On Reconfiguring Tree Linkages: Trees can Lock (2000)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. In this paper we propose a related question: whether a...
On Reconfiguring Tree Linkages: Trees can Lock (1999)
Biedl, Therese, Demaine, Erik, Demaine, Martin, Lazard, Sylvain, Lubiw, Anna, O'Rourke, Joseph, ...
It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex....
Motion Planning of Legged Robots (1999)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space F of a simple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is...
Convexifying Monotone Polygons (1999)
Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss
This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a...
Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract) (1998)
Pankaj K. Argarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides
) Pankaj K. Agarwal Therese Biedl y Sylvain Lazard z Steve Robbins x Subhash Suri -- Sue Whitesides k Abstract Let B be a point robot moving in the plane, whose path is constrained to have curvature...
On Reconfiguring Tree Linkages: Trees can Lock (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna Lubiw, Steve Robbins, ...
It is an open problem to determine whether a polygonal chain can be "straightened" in the plane if its links are not allowed to cross. This problem been raised independently by several...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Motion Planning of Legged Robots (1997)
Boissonnat, Jean-Daniel, Devillers, Olivier, Lazard, Sylvain
We study the problem of computing the free space \Fsimple legged robot called the spider robot. The body of this robot is a single point and the legs are attached to the body. The robot is subject to...
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....
Boissonnat, Jean-Daniel, Lazard, Sylvain
In this paper, we consider the problem of computing a shortest path of bounded curvature amidst obstacles in the plane. More precisely, given prescribed initial and final configurations (i.e....