8th McGill - INRIA Workshop on Computational Geometry

Bellairs Research Institute of McGill University
31 January to 6 February 2009

Previous workshops

List of Participants

  • Helmut Alt, Freie Universität Berlin
  • Nina Amenta, University of California at Davis
  • Boris Aronov, Polytechnic Institute of New York University
  • Dominique Attali, CNRS, Gipsa-Lab, Grenoble
  • David Bremner, University of New Brunswick
  • Erin Chambers, Saint Louis University
  • Otfried Cheong, KAIST, South Korea
  • Mark de Berg, TU Eindhoven
  • Olivier Devillers, INRIA Sophia Antipolis - Méditerranée
  • Al Erickson, University of Waterloo
  • Will Evans, University of British Columbia
  • Hazel Everett, LORIA, Nancy
  • Sandor Fekete, TU Braunschweig
  • Xavier Goaoc, INRIA Nancy-Grand Est, LORIA, Nancy
  • Danny Halperin, Tel Aviv University
  • Sariel Har-Peled, University of Illinois at Urbana-Champaign
  • David Kirkpatrick, University of British Columbia
  • Sylvain Lazard, INRIA Nancy-Grand Est, LORIA, Nancy
  • Jon Lenchner, IBM, USA
  • Giuseppe Liotta, Universitā di Perugia
  • Anna Lubiw, University of Waterloo
  • Wendy Myrvold, University of Victoria
  • Raimund Seidel, Universität des Saarlandes
  • Jeff Sember, University of British Columbia
  • Venkatesh Srinivasan, University of Victoria
  • Ulrike Stege, University of Victoria
  • Svetlana Stolpner, McGill University
  • Christophe Weibel, McGill University
  • Sue Whitesides, McGill University
  • Steven Wismath, University of Lethbridge
  • Camille Wormser, ETH Zürich
  • Linqiao Zhang, McGill University


Visibility problems concerning one-sided segments, Jon Lenchner

Background reading

Will Evans is suggesting the following :

Largest and Smallest Convex Hulls for Imprecise Points by Loffler and van Kreveld

Guaranteed Voronoi Diagrams of Uncertain Sites by Evans and Sember

Delaunay Triangulations of Imprecise Points in Linear Time after Preprocessing by Loffler and Snoeyink

A Survey of Performance Measures for On-line Algorithms by Dorrigiv and Lopez-Ortiz

Epsilon Geometry: Building Robust Algorithms from Imprecise Computations by Guibas, Salesin and Stolfi

Further suggestions :

Inner and Outer Rounding of Set Operations on Lattice Polygonal Regions by Devillers and Guigue

Finding Compact Coordinate Representations for Polygons and Polyhedra by Milenkovic and Nackman

Contribution from Danny Halperin

Snap rounding is a fairly successful geometric rounding scheme (it caught on quite a bit). There are about a douzen papers published on it, of which I mention only three below.

Improved Output-Sensitive Snap Rounding, John Hershberger. DCG 39(1-3) 298-318 (2008). (Recent efficient algorithms for arrangements of segments in the plane.)

Iterated Snap Rounding with Bounded Drift, Eli Packer,CG 40(3) 231-251 (2008). (Better quality rounding for arrangements of segments in the plane.)

Vertex-Rounding a Three-Dimensional Polyhedral Subdivision. Steven Fortune, DCG 22(4) 593-618 (1999). (Snap rounding in 3D; rather costly though.)

Assembly sequencing with toleranced parts, Jean-Claude Latombe, Randall H. Wilson, Frederic Cazals, CAD 29(2) 159-174(1997). (Addresses the problem of assembly sequencing under uncertainty in parts shape.)

Practical Information

Click here.