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...
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
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 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...
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...
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...
Abstract Predicates for Line Transversals in 3D (2008)
Hazel Everett, Sylvian Lazard, Bill Lenhart, Jeremy Redburn, Linqiao Zhang
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...
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 Predicates for Line Transversals in 3D (2008)
Hazel Everett, Sylvian Lazard, Bill Lenhart, Jeremy Redburn, Linqiao Zhang
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...
Abstract Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2008)
Olivier Devillers, Vida Dujmović, Hazel Everett, Samuel Hornus, Sue Whitesides
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. 1
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...
The Union of Moving Polygonal Pseudodiscs { Combinatorial Bounds and Applications (2008)
Mark Berg, Hazel Everett, Leonidas J. Guibas
Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with xed velocities in xed directions. We prove that the maximum number of combinatorial changes in the union of...
An Optimal Algorithm for Finding Clique-Cross Partitions (2008)
Hazel Everett, Sulamita Klein, Bruce Reed
We consider the problem of determining whether or not the vertices of a graph can be partitioned into four disjoint cliques A; B; C; D such that vertices of A are not adjacent to vertices of C and...
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...
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...
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...
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$...
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$...
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...
Olivier Devillers, Vida Dujmovi C, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-suk Na, ...
A linear bound on the expected
Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Tom Shermer, Sue Whitesides
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
Mark De Berg, Hazel Everett, Leonidas J. Guibas
Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with fixed velocities in fixed directions. We prove that the maximum number of combinatorial changes in the...
Hierarchical Decompositions and Circular Ray Shooting in (2007)
Siu-wing Cheng, Otfried Cheong, Hazel Everett
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray...
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, 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...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2007)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves. In...
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...
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)...
Parabola separation queries and their application to stone throwing (2007)
Cheong, Otfried, Everett, Hazel, Kim, Hyo-Sil, Lazard, Sylvain, Schott, René
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...
Parabola separation queries and their application to stone throwing (2007)
Cheong, Otfried, Everett, Hazel, Kim, Hyo-Sil, Lazard, Sylvain, Schott, René
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...
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})....
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...
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, 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...
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...
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)$.
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...
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)$.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
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...
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...
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)$.
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...
Optimal Spanners for Axis-Aligned Rectangles (2005)
Asano, Tetsuo, De Berg, Mark, Cheong, Otfried, Everett, Hazel, Haverkort, Herman, Katoh, Naoki, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
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})$.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
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})$.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
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...
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)$.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Whitesides, Sue, Wismath, Steve
Given a set of $n$ points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint $q$ and efficiently maintaining this ordering information as $q$...
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...
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)$.
Maintaining Visibility Information of Planar Point Sets with a Moving Viewpoint (2005)
Devillers, Olivier, Dujmovic, Vida, Everett, Hazel, Hornus, Samuel, Wismath, Steve, Whitesides, Sue
Given a set of n points in the plane, we consider the problem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this ordering information as q moves.
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).
Maintaining visibility information of planar point sets with a moving viewpoint (2005)
Olivier Devillers, Hazel Everett, Samuel Hornus, Sue Whitesides, Steve Wismathk
Abstract Given a set of n points in the plane, we consider theproblem of computing the circular ordering of the points about a viewpoint q and efficiently maintaining this or-dering information as q...
Optimal spanners for axis-aligned rectangles (2005)
Alexander Wol, Tetsuo Asano, Tetsuo Asano, Mark De Berg, Mark De Berg, Otfried Cheong, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Optimal spanners for axis-aligned rectangles (2005)
Tetsuo Asano, Mark Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
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).
Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons (2004)
Cheng, Siu-Wing, Cheong, Otfried, Everett, Hazel, Van Oostrum, René
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray...
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...
Siu-wing Cheng, Otfried Cheong, Hazel Everett
Ren'e van Oostrum 2 A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have at most three neighbors. Using this...
Siu-wing Cheng, Otfried Cheong, Hazel Everett, Ren Oostrum
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(logn), linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting...
Optimal Spanners for Axis-Aligned Rectangles (2004)
Tetsuo Asano, Markk De Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, ...
this paper: we assume the topology of the network (the bridge graph) is given, and our only task is to place the bridges so as to minimize the dilation
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
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...
Hierarchical decompositions and circular ray shooting in simple polygons (2002)
Cheng, Siu-Wing, Cheong, Otfried, Everett, Hazel, Van Oostrum, Rene
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(log n), linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray...
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...
Hazel Everett, Claudia Linhares Sales, Frederic Maffray, Oscar Porto, Cl'audia Linhares Sales, ...
Two non-adjacent vertices in a graph form an even pair if every chordless path between them has an even number of edges. The salient fact about even pairs is that contracting an even pair in a graph...
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...
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...
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...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Anna Lubiw, Henk Meijer, Kathleen Romanik, Thomas C. Shermer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles oating in R
The Homogeneous Set Sandwich Problem (1998)
Marcia R. Cerioli, Hazel Everett, Sulamita Klein
The graph sandwich problem for property \Phi is defined as follows: Given two graphs G 1 = (V; E 1 ) and G 2 = (V; E 2 ) such that E 1 ` E 2 , is there a graph G = (V; E) such that E 1 ` E ` E 2...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
Angewandte Mathematik und Informatik Universit at zu K oln (1997)
Report No On, Hazel Everett, Hazel Everett, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...
On a Visibility Representation of Graphs in 3D (1997)
Prosenjit Bose, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V; E) in which vertices are mapped to rectangles floating in R 3 parallel to the x; y-plane, with edges represented by...
Path Parity and Perfection (1996)
Hazel Everett, Claudia Linhares-Sales, Frederic Maffray, Oscar Porto, Bruce A. Reed
Two non-adjacent vertices x and y in a graph G form an even pair if every induced path between them has an even number of edges. For a given pair fx; yg in a graph G, we denote by G xy the graph...
Angewandte Mathematik und Informatik Universit at zu K oln (1995)
Report No On, Qu'ebec Ga H, Hazel Everett, Hazel Everett, S'andor P. Fekete, S'andor P. Fekete, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
On a Visibility Representation for Graphs in Three Dimensions (1995)
Prosenjit Bose, Qu'ebec Ga H, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
Illuminating The Free Space Between Quadrilaterals With Point Light Sources (1994)
Gregoria Blanco, Hazel Everett, Jesus Garcia Lopez, Godfried Toussaint
Let S be a set of n pairwise-disjoint, possibly non-convex, quadrilaterals in the plane. We consider the problem of illuminating the "free" space, i.e., the region of the plane excluding...
On a Visibility Representation for Graphs in Three Dimensions (1993)
Prosenjit Bose, Hazel Everett, Sandor P. Fekete, Anna Lubiw, Henk Meijer, Kathleen Romanik, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
A Counter-example to a Dynamic Algorithm for Convex Hulls of Line Arrangements (1991)
Binay Bhattacharya, Hazel Everett, Godfried Toussaint
An algorithm was recently published to maintain dynamically the convex hull of the set I of intersection points of a set L of n lines in the plane [Bo90]. In other words, given the convex hull of I...
A Counter-example to a Dynamic Algorithm for Convex Hulls of Line Arrangements (1991)
Binay Bhattacharya, Hazel Everett, Godfried Toussaint
An algorithm was recently published to maintain dynamically the convex hull of the set I of intersection points of a set L of n lines in the plane [Bo90]. In other words, given the convex hull of I...
The Graham Scan Triangulates Simple Polygons (1991)
Xianshu Kong, Hazel Everett, Godfried Toussaint
The Graham scan is a fundamental backtracking technique in computational geometry which was originally designed to compute the convex hull of a set of points in the plane and has since found...
Slicing an Ear in Linear Time (1989)
Hossam ElGindy, Hazel Everett, Godfried Toussaint
It remains as one of the major open problems in computational geometry, whether there exists a linear-time algorithm for triangulating a simple polygon P. Yet it is well known that a diagonal of P...