9th McGill - INRIA Workshop on Computational Geometry

Bellairs Research Institute of McGill University
 29 January to 5 February 2010

Previous workshops

List of Participants

  • Helmut Alt, Freie Universität Berlin
  • Dominique Attali, CNRS, Gipsa-Lab, Grenoble
  • David Bremner, University of New Brunswick
  • Mark de Berg, TU Eindhoven
  • Olivier Devillers, INRIA Sophia Antipolis - Méditerranée
  • Vida Dujmovic, Carleton University
  • Al Erickson, University of Waterloo
  • Will Evans, University of British Columbia
  • Hazel Everett, LORIA, Nancy
  • Panos Gianopoulos, Freie Universität Berlin
  • Marc Glisse, INRIA Saclay
  • Xavier Goaoc, INRIA Nancy-Grand Est, LORIA
  • Stephan Kobourov, University of Arizona
  • Sylvain Lazard, INRIA Nancy-Grand Est, LORIA, Nancy
  • Giuseppe Liotta, Universitā di Perugia
  • Jarek Rossignac, Georgia Tech
  • Frank Ruskey, University of Victoria
  • Raimund Seidel, Universität des Saarlandes
  • Ulrike Stege, University of Victoria
  • Svetlana Stolpner, McGill University
  • Christophe Weibel, McGill University
  • Sue Whitesides, McGill University
  • Steven Wismath, University of Lethbridge
  • Brian Wyvill, University of Victoria
  • Linqiao Zhang, McGill University

Background reading

Jarek Rossignac is suggesting that the following two papers, downloadable from http://www.gvu.gatech.edu/~jarek/papers.html, will be relevant :

B-morphs between b-compatible curves, B. Whited, J. Rossignac, ACM Symposium on Solid and Physical Modeling (SPM), 2009.

SOT: Compact representation for Tetrahedral Meshes, T. Gurung, J. Rossignac, ACM Symposium on Solid and Physical Modeling (SPM), 2009.

Further reading

Olivier Devillers has put together the following list of interesting papers on the topic of geometry and probability :

Convex hulls

Valentina Damerow and Christian Sohler. Extreme points under random noise. Proc. 12th European Symposium on Algorithms, pages 264--274, 2004.

Sariel Har-Peled. On the expected complexity of random convex hulls, 1997. http://valis.cs.uiuc.edu/~sariel/research/papers/notes/rand_hull.html.

H. Raynaud. Sur l'enveloppe convexe des nuages de points aléatoires dans R^n. J. Appl. Probab., 7:35--48, 1970.

A. Renyi and R.Sulanke. Uber die konvexe Hulle von n zufallig gerwahten Punkten I. Z. Wahrsch. Verw. Gebiete, 2:75--84, 1963.

Point location in Delaunay

Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181--199, 2002.

Luc Devroye, Christophe Lemaire, and Jean-Michel Moreau. Expected time analysis for Delaunay point location. Comput. Geom. Theory Appl., 29:61--89, 2004.

Ernst P. Mucke, Isaac Saias, and Binhai Zhu. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. Proc. 12th Annu. Sympos. Comput. Geom., pages 274--283, 1996.

Delaunay complexity

Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pages 1106--1113, 2007.

Dominique Attali and Jean-Daniel Boissonnat. Complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete and Computational Geometry, 30(3):437--452, 2003.

Dominique Attali, Jean-Daniel Boissonnat, and Andre Lieutier. Complexity of the Delaunay triangulation of points on surfaces: The smooth case. Proc. 19th Annual Symposium on Computational Geometry, pages 237--246, 2003.

J.-D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete and Computational Geometry, 8:51--71, 1992.

Olivier Devillers, Jeff Erickson, and Xavier Goaoc. Empty-ellipse graphs. Proc. 19th ACM-SIAM Sympos. Discrete Algorithms, pages 1249--1256, 2008.

R. A. Dwyer. Higher-dimensional Voronoi diagrams in linear expected time. Discrete Comput. Geom., 6:343--367, 1991.

Jeff Erickson. Nice point sets can have nasty Delaunay triangulations. Proc. 17th Annu. Sympos. Comput. Geom., pages 96--105, 2001.

Mordecai J. Golin and Hyeon-Suk Na. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Proc. 12th Annu. Sympos. Comput. Geom., pages 127--135, 2000.

Practical Information

Click here.