Xavier Goaoc

Lower Bounds for Pinning Lines by Balls (2009)

A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint...

Lower Bounds for Pinning Lines by Balls (2009)

A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint...

Helly-type theorems for approximate covering (2009)

A line L is a transversal to a family F of convex objects in R^d if it intersects every member of F. In this paper we show that for every integer d>2 there exists a family of 2d-1 pairwise disjoint...

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...

Computing Direct Shadows Cast by Convex Polyhedra (2009)

Demouth, Julien, Goaoc, Xavier

We present an exact method to compute the boundaries between umbra, penumbra and full-light regions cast on a plane by a set of disjoint convex polyhedra, some of which are light sources. This method...

Lower Bounds for Pinning Lines by Balls (Extended Abstract) (2009)

Computing Direct Shadows Cast by Convex Polyhedra (2009)

It is known that if n>=2d pairwise disjoint balls in R^d have a unique line ℓ intersecting them in a given order

Demouth, Julien, Goaoc, Xavier

We present an exact method to compute the boundaries between umbra, penumbra and full-light regions cast on a plane by a set of disjoint convex polyhedra, some of which are light sources. This method...

Lower Bounds for Pinning Lines by Balls (Extended Abstract) (2009)

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls (2008)

It is known that if n>=2d pairwise disjoint balls in R^d have a unique line ℓ intersecting them in a given order

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in Rd . In particular, we show that a family of n ≥ 2d disjoint unit balls in Rd has a line transversal if, for some...

Moving Vertices to Make Drawings Plane (2008)

Goaoc, Xavier, Kratochvíl, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander

In John Tantalo's on-line game $Planarity$ the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In...

Hadwiger and Helly-type theorems for disjoint unit spheres (2008)

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in $\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit balls in $\R^d$ has a line transversal if, for...

Hadwiger and Helly-type theorems for disjoint unit spheres (2008)

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in $\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit balls in $\R^d$ has a line transversal if, for...

Line transversals to disjoint balls (2008)

Empty-ellipse graphs (2008)

We prove that the set of directions of lines intersecting three disjoint balls in $\mathbb{R}^3$ in a given order is a strictly convex subset of $\mathbb{S}^2$. We then generalize this result to $n$...

Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P...

Line transversals to disjoint balls (2008)

Empty-ellipse graphs (2008)

We prove that the set of directions of lines intersecting three disjoint balls in $\mathbb{R}^3$ in a given order is a strictly convex subset of $\mathbb{S}^2$. We then generalize this result to $n$...

Devillers, Olivier, Erickson, Jeff, Goaoc, Xavier

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P...

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...

Moving Vertices to Make Drawings Plane (2008)

Goaoc, Xavier, Kratochvíl, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander

In John Tantalo's on-line game $Planarity$ the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In...

Empty-Ellipse Graphs (2008)

Olivier Devillers, Jeff Erickson, Xavier Goaoc

We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in IR 3. Two points in a planar point set P are...

Some discrete properties of the space of line transversals to disjoint balls (2008)

Xavier Goaoc

Abstract. Attempts to generalize Helly’s theorem to sets of lines intersecting convex sets led to a series of results relating the geometry of a family of sets in R d to the structure of the space...

Inflating balls is NP-hard (2008)

Batog, Guillaume, Goaoc, Xavier

A collection C of balls in R^d is \delta-inflatable if it is isometric to the intersection U \cap E of some d-dimensional affine subspace E with a collection U of (d+\delta)-dimensional balls that...

Inflating balls is NP-hard (2008)

Batog, Guillaume, Goaoc, Xavier

A collection C of balls in R^d is \delta-inflatable if it is isometric to the intersection U \cap E of some d-dimensional affine subspace E with a collection U of (d+\delta)-dimensional balls that...

Some Discrete Properties of the Space of Line Transversals to Disjoint Balls (2008)

Goaoc, Xavier

Attempts to generalize Helly's theorem to sets of lines intersecting convex sets led to a series of results relating the geometry of a family of sets in R^d to the structure of the space of lines...

There are arbitrary large minimal 2-pinning configurations (2008)

Goaoc, Xavier, Hyo-Sil, Kim, Jung-Gun, Lim

We characterize minimal configurations that pin a line in every $2$-plane.

Some Discrete Properties of the Space of Line Transversals to Disjoint Balls (2008)

Goaoc, Xavier

Attempts to generalize Helly's theorem to sets of lines intersecting convex sets led to a series of results relating the geometry of a family of sets in R^d to the structure of the space of lines...

There are arbitrary large minimal 2-pinning configurations (2008)

Goaoc, Xavier, Hyo-Sil, Kim, Jung-Gun, Lim

We characterize minimal configurations that pin a line in every $2$-plane.

x (2007)

Olivier Devillers, Vida Dujmovi C, Hazel Everett, Xavier Goaoc, Sylvain Lazard, Hyeon-suk Na, ...

A linear bound on the expected

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...

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Untangling a Planar Graph (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Goaoc, Xavier, Kratochvil, Jan, Okamoto, Yoshio, Shin, Chan-Su, Spillner, Andreas, Wolff, Alexander

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by \emph{untangling} it, that is, by moving some of the vertices of $G$. Let shift$(G,\delta)$ denote the...

Moving Vertices to Make Drawings Plane (2007)

Goaoc, Xavier, Kratochvil, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander

A straight-line drawing $\delta$ of a planar graph $G$ need not be plane, but can be made so by moving some of the vertices. Let shift$(G,\delta)$ denote the minimum number of vertices that need to...

Hadwiger and Helly-type theorems for disjoint unit spheres (2007)

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in $\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit balls in $\R^d$ has a line transversal if, for...

Line transversals to disjoint balls (2007)

Line transversals to disjoint balls (2007)

We prove that the set of directions of lines intersecting three disjoint balls in $\mathbb{R}^3$ in a given order is a strictly convex subset of $\mathbb{S}^2$. We then generalize this result to $n$...

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

We prove that the set of directions of lines intersecting three disjoint balls in $\mathbb{R}^3$ in a given order is a strictly convex subset of $\mathbb{S}^2$. We then generalize this result to $n$...

Random sampling of a cylinder yields a not so nasty Delaunay triangulation (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

Helly-type theorems for approximate covering (2007)

We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of...

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...

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...

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...

Moving vertices to make drawings plane (2007)

Goaoc, Xavier, Kratochvil, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In...

Moving vertices to make drawings plane (2007)

Goaoc, Xavier, Kratochvil, Jan, Okamoto, Yoshio, Shin, Chan-Su, Wolff, Alexander

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. In...

Line transversals to disjoint balls (2006)

A note on maximally repeated sub-patterns of a point set (2006)

We prove that the set of directions of lines intersecting three disjoint balls in $R^3$ in a given order is a strictly convex subset of $S^2$. We then generalize this result to $n$ disjoint balls in...

Goaoc, Xavier, Cortier, Véronique, Lee, Mira, Hyeon-Suk, Na

We answer a question raised by P.~Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\R^d$. We show that this number, which was conjectured to be polynomial, is in fact...

A note on maximally repeated sub-patterns of a point set (2006)

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Hyeon-Suk, Na

We answer a question raised by P.~Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\R^d$. We show that this number, which was conjectured to be polynomial, is in fact...

A note on maximally repeated sub-patterns of a point set (2006)

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Hyeon-Suk, Na

We answer a question raised by P.~Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\R^d$. We show that this number, which was conjectured to be polynomial, is in fact...

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.

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.

A note on maximally repeated sub-patterns of a point set (2006)

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Hyeon-Suk, Na

We answer a question raised by P.~Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\R^d$. We show that this number, which was conjectured to be polynomial, is in fact...

Helly-type Theorems for Line transversals to Disjoint Unit Balls (2006)

Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean

We prove Helly-type theorems for line transversals to disjoint unit balls in R d. In particular, we show that a family of n � 2d disjoint unit balls in R d has a line transversal if, for some...

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...

Helly-type Theorems for Line transversals to Disjoint Unit Balls (2006)

Otfried Cheong, Xavier Goaoc, Andreas Holmsen, Sylvain Petitjean

We prove Helly-type theorems for line transversals to disjoint unit balls in R d. In particular, we show that a family of n � 2d disjoint unit balls in R d has a line transversal if, for some...

Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract) (2006)

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in R^d. In particular, we show that a family of n >= 2d disjoint unit balls in Rd has a line transversal if, for some...

Helly-type Theorems for Line transversals to Disjoint Unit Balls (Extended abstract) (2006)

Cheong, Otfried, Goaoc, Xavier, Holmsen, Andreas, Petitjean, Sylvain

We prove Helly-type theorems for line transversals to disjoint unit balls in R^d. In particular, we show that a family of n >= 2d disjoint unit balls in Rd has a line transversal if, for some...

A note on maximally repeated sub-patterns of a point set (2005)

Cortier, Véronique, Goaoc, Xavier, Na, Hyeon-Suk, Lee, Mira

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is...

A note on maximally repeated sub-patterns of a point set (2005)

Cortier, Véronique, Goaoc, Xavier, Na, Hyeon-Suk, Lee, Mira

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is...

A note on maximally repeated sub-patterns of a point set (2005)

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Na, Hyeon-Suk

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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...

Hadwiger and Helly-type theorems for disjoint unit spheres in R3 (2005)

Geometric Permutations of Disjoint Unit Spheres (2005)

Let S be an ordered set of disjoint unit spheres in R3 We show that if every subset of at most six spheres from S admits a line transversal respecting the ordering, then the entire family has a line...

Geometric Permutations of Disjoint Unit Spheres (2005)

We show that a set of $n$ disjoint unit spheres in $R^d$ admits at most two distinct geometric permutations if $n \geq 9$, and at most three if $3 \leq n \leq 8$. This result improves a Helly-type...

Geometric Permutations of Disjoint Unit Spheres (2005)

We show that a set of n disjoint unit spheres in Click to view the MathML source admits at most two distinct geometric permutations if ngreater-or-equal, slanted9, and at most three if...

Hadwiger and Helly-type theorems for disjoint unit spheres in R3 (2005)

We show that a set of $n$ disjoint unit spheres in $R^d$ admits at most two distinct geometric permutations if $n \geq 9$, and at most three if $3 \leq n \leq 8$. This result improves a Helly-type...

A note on maximally repeated sub-patterns of a point set (2005)

Let S be an ordered set of disjoint unit spheres in R3 We show that if every subset of at most six spheres from S admits a line transversal respecting the ordering, then the entire family has a line...

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Na, Hyeon-Suk

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is...

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

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...

Geometric Permutations of Disjoint Unit Spheres (2005)

On the Number of Maximal Free Line Segments Tangent to Arbitrary Three-dimensional Convex Polyhedra (2005)

We show that a set of $n$ disjoint unit spheres in $R^d$ admits at most two distinct geometric permutations if $n \geq 9$, and at most three if $3 \leq n \leq 8$. This result improves a Helly-type...

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...

A note on maximally repeated sub-patterns of a point set (2005)

Cortier, Véronique, Goaoc, Xavier, Lee, Mira, Na, Hyeon-Suk

We answer a question raised by P. Brass on the number of maximally repeated sub-patterns in a set of $n$ points in $\mathbbR^d$. We show that this number, which was conjectured to be polynomial, is...

Hadwiger and Helly-type theorems for disjoint unit spheres in R3 (2005)

Common Tangents to Spheres in R^3 (2004)

Let S be an ordered set of disjoint unit spheres in R3 We show that if every subset of at most six spheres from S admits a line transversal respecting the ordering, then the entire family has a line...

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.

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...

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...

Disjoint Unit Spheres admit at most two Line Transversals (2003)

Disjoint Unit Spheres admit at most two Line Transversals (2003)

We show that a set of n disjoint unit spheres in admits at most two distinct geometric permutations, or line transversals, if n is large enough. This bound is tight.

Disjoint Unit Spheres admit at most two Line Transversals (2003)

We show that a set of n disjoint unit spheres in admits at most two distinct geometric permutations, or line transversals, if n is large enough. This bound is tight.

Disjoint Unit Spheres Admit At Most Two Line Transversals (2003)

We show that a set of n disjoint unit spheres in admits at most two distinct geometric permutations, or line transversals, if n is large enough. This bound is tight.

Disjoint Unit Spheres Admit At Most Two Line Transversals (2003)

We show that a set of $n$~disjoint unit spheres in $\Rd$ admits at most \emph{two} distinct geometric permutations, or line transversals, if $n$ is large enough. This bound is optimal.