Image by Nadia Benbernou, Patricia Cahn, Joseph O'Rourke

14th Annual Fall Workshop on Computational Geometry

with a Focus on Open Problems

November 19-20, 2004

Massachusetts Institute of Technology
Room 141, Building 32, The Stata Center
32 Vassar Street
Cambridge, MA 02139 USA

Accepted Abstracts

  1. The Metric TSP and the Sum of its Marginal Values by Moshe Dror, Yusin Lee, and James B. Orlin
  2. Unfolding Smooth Prismatoids by Nadia Benbernou, Patricia Cahn, and Joseph O'Rourke
  3. Topologically Sweeping the Complete Graph in Optimal Time by Eynat Rafalin and Diane Souvaine
  4. OrthoMap: Homeomorphism-guaranteeing normal-projection map between surfaces by F. Chazal, A. Lieutier, and J. Rossignac
  5. Dynamic Update of Half-space Depth Contours by M. Burr, E. Rafalin, and D. L. Souvaine
  6. Floodlight Illumination of Infinite Wedges by Matthew Cary, Atri Rudra, Ashish Sabharwal, and Erik Vee
  7. Optimal Area Triangulation with Angular Constraints by J. Mark Keil and Tzvetalin S. Vassilev
  8. Drawing Equally-Spaced Curves between Two Points by Tetsuo Asano and Takeshi Tokuyama
  9. Pointed Binary Encompassing Trees: Simple and Optimal by Michael Hoffmann and Csaba Toth
  10. Detecting Duplicates Among Similar Bit Vectors (of course, with geometric applications) by Boris Aronov and John Iacono
  11. Computing a Point of High Simplicial Depth in R^2 by Jason Burrowes-Jones and William Steiger
  12. An Efficient k-center clustering Algorithm for Geometric Objects by Guang Xu and Jinhui Xu
  13. Fast almost-linear-sized nets for boxes in the plane by Hervé Brönnimann and Jonathan Lenchner
  14. Parallel Guaranteed Quality Planar Delaunay Mesh Generation by Concurrent Point Insertion by Andrey N. Chernikov and Nikos P. Chrisochoides
  15. A Distributed Architecture for the Visualization of Geometric Models by Sourav Dalal, Frank Devai, and Md Mizanur Rahman
  16. Approximation Algorithms for Two Optimal Location Problems in Sensor Networks by Alon Efrat, Sariel Har-Peled, and Joseph S. B. Mitchell
  17. Analysis of Layered Hierarchy for Necklaces by Kathryn Bean and Sergey Bereg
  18. Hinged Dissection of Polypolyhedra by Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine
  19. Nearest Point Query in E^3 with a Uniform Grid by W. Randolph Franklin
  20. Tightening: Curvature-Limiting Morphological Simplification by Jason Williams and Jarek Rossignac
  21. Algebraic Number Comparisons for Robust Geometric Operations by John Keyser and Koji Ouchi
  22. Grid Edge-Unfolding Orthostacks with Orthogonally Convex Slabs by Mirela Damian and Henk Meijer
  23. Proximity Problems on Line Segments Spanned by Points by Ovidiu Daescu and Jun Luo
  24. Hamiltonian Cycles in Sparse Vertex-Adjacency Duals by Perouz Taslakian and Godfried Toussaint
  25. Trees on Tracks by Justin Cappos and Stephen Kobourov
  26. A 2-chain Can Interlock with a k-chain by Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, and Jianyuan K. Zhong
  27. Provably Better Moving Least Squares by Ravikrishna Kolluri, James F. O'Brien, and Jonathan R. Shewchuk
  28. Farthest Point from Line Segment Queries by Ovidiu Daescu and Robert Serfling
  29. On the non-redundancy of split offsets in degree coding by Martin Isenburg and Jack Snoeyink
  30. Folding Paper Shopping Bags by Devin J. Balkcom, Erik D. Demaine, and Martin L. Demaine
  31. Contour Tree Simplification With Local Geometric Measures by Hamish Carr, Jack Snoeyink, and Michiel van de Panne