Others Results

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and 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 point on it. We showed in (i) that the complexity of this diagram is O(n), and give an O(n log3 n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k-1 connected components, but if one component is bounded, then it is equal to the entire region. This problem can be seen as non-linear as the arcs of the diagrams are parabolic; this is however stretched because the techniques we use are rather standard in computational geometry, except perhaps an application of parametric search on parabolic arcs.
  1. Farthest-Polygon Voronoi Diagrams

Homotopic Frechet distance between curves

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 backtracking. We proposed in (i) a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of polygonal obstacles.
  1. Erin Wolf Chambers, Eric Colin De Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite

Graph drawing

We showed 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; in other words, we exhibit size-n point sets on which any graph can be embedded. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge. We also considered the following problem: given a non-plane straight-line drawing of a planar graph with n vertices, identify the minimum number of vertices that needs to be moved to remove all crossings (once a vertex is moved, the incident edges are redrawn from the new position as straight-line segments). We proved that the corresponding decision problem is NP-complete, showed that the minimum number of moves cannot be approximated within a factor n1-ε unless P=NP, and analyzed restrictions of the problem to various particular classes of graphs.
  1. Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Steve Wismath
  2. Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, Alexander Wolff

Empty-ellipse graphs

The Delaunay triangulation of n points in R3 can have complexity Θ(n)2, but this bound is often observed to be pessimistic in practical situations, in particular when the points are obtained by sampling a surface. A natural approach to explain this discrepancy is to analyze the expected complexity of the Delaunay triangulation of random samples of reasonnable surfaces. For generic surfaces this expected complexity was shown to be O(n log3n) [Attali et al. 2003]. Here, generic means that no sphere is tangent to the surface in infinitely many point. We made a step toward relaxing this condition by proving that the expected complexity of the Delaunay triangulation of n points uniformly distributed on a constant-height right cylinder, one of the model non-generic surfaces, is Θ(n log n). We showed this by sandwiching the Delaunay triangulation between other empty-region graphs easier to study.