Olivier Devillers, Marc Glisse, Sylvain Lazard
for line transversals to lines and line segments
Helly-type theorems for approximate covering (2009)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...
Helly-type theorems for approximate covering (2009)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...
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 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...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
1 Introduction Cost-Optimal Quadtrees for Ray Shooting ∗ (2008)
Hervé Brönnimann, Marc Glisse, David R. Wood
Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the first
Julien Demouth, Marc Glisse, Between Umbra
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...
Cost-Optimal Quadtrees for Ray Shooting \Lambda Herv'e Br"onnimann y (2008)
R. Wood z 1 Introduction Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the first object in S intersected by this ray. A popular approach to speed up...
Helly-type theorems for approximate covering (2008)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...
Helly-type theorems for approximate covering (2008)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume...
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...
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,...
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,...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Proximity of Persistence Modules and their Diagrams (2008)
Chazal, Frédéric, Cohen-Steiner, David, Glisse, Marc, Guibas, Leonidas J., Oudot, Steve
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence...
Combinatoire des droites et segments pour la visibilité 3D (2007)
Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous...
Cost-Optimal Quadtrees for Ray Shooting Herve Bronnimann y (2007)
Given a set S of objects, called a scene, the rayshooting problem asks, given a ray, what is the rst object in S intersected by this ray. A popular approach
Cost-Optimal Quadtrees for Ray Shooting (2007)
Hervé Brönnimann, Marc Glisse, David R. Wood
this paper, the only objects we consider are simplices (points and segments inside the unit square [0; 1] in R , or points, segments and triangles inside the unit cube [0; 1] in R ). We denote the...
On the theoretical complexity of the silhouette of a polyhedron Mémoire soutenu le vendredi 5 septembre 2003 par
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
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,...
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...
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
Helly-type theorems for approximate covering (2007)
Demouth, Julien, Devillers, Olivier, Glisse, Marc, Goaoc, Xavier
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size...
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...
Combinatoire des droites et segments pour la visibilité 3D (2007)
Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous...
Combinatoire des droites et segments pour la visibilité 3D (2007)
Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous...
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...
Combinatoire des droites et segments pour la visibilité 3D (2007)
Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous...
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...
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...
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...
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...
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...
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...
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...
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...
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...
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...
Cost-optimal trees for ray shooting, in (2004)
Abstract. Predicting and optimizing the performance of ray shooting is a very important problem in computer graphics due to the severe computational demands of ray tracing and other applications,...
On the Worst-Case Complexity of the Silhouette of a Polytope (2003)
Helmut Alt, Marc Glisse, Xavier Goaoc
We give conditions under which the worst-case size of the silhouette of a polytope is sub-linear. We provide examples with linear size silhouette if any of these conditions is relaxed. Our bounds are...