DIMACS Workshop on Computational Geometry

November 14 - 15, 2002
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:: Joseph S. B. Mitchell, Stony Brook University, jsbm@ams.sunysb.edu
Program Committee:: Herve Bronnimann, Polytechnic University; Erik Demaine, MIT; Steven Fortune, Bell Laboratories; Joseph S. B. Mitchell, Stony Brook University; Ileana Streinu, Smith College; Suresh Venkatasubramanian, AT&T

Presented under the auspices of the Special Focus on Computational Geometry and Applications.

Final Workshop Program


Thursday, November 14

8:00-8:50    Continental Breakfast 

8:50-9:00    Opening Remarks 

9:00-10:00   Contributed talks: 
             The Path of a Pseudo-Triangulation
             Oswin Aichholzer, Ileana Streinu, and Bettina Speckmann 
 
             An Energy-Driven Approach to Linkage Unfolding
             Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, and James F. O'Brien 
 
             Proximate Planar Point Location
             John Iacono and Stefan Langerman. 
             
             Exact Algorithms for Computing the Location Depth and the k-th
               Depth Regions Based on Parallel Arrangement Constructions
             Komei Fukuda and Vera Rosta 

10:00-10:30  Break 

10:30-11:20  Invited Talk: Regina Liu (Rutgers): 
             Data Depth in Multivariate Data Analysis: Usefulness and Challenges

11:20-11:30  Minibreak 

11:30-12:30  Contributed talks: 
 
             Several Geometric Tiling and Packing Problem With Applications To 
               Nonoverlapping local alignments, DNA microarray designs and
               Homology Searches
             Bhaskar DasGupta 

             Art Gallery Theorems for Guarded Guards
             T. S. Michael and Val Pinciu 
 
             Matching Planar Maps
             Helmut Alt, Alon Efrat, G\"unter Rote, and Carola Wenk 
 
             Approximation Algorithms for Aligning Points
             Sergio Cabello and Marc van Kreveld 

12:30-2:00   Lunch 

2:00-2:50    Invited Talk: Timothy Chan (Waterloo): 
             Low-Dimensional Linear Programming with Violations

2:50-3:00    Minibreak 

3:00-4:00    Contributed talks: 

             The Rectilinear Minimum Bends Path Problem in Three Dimensions
             David P. Wagner, Robert Scot Drysdale, and Clifford Stein 

             Fault-Tolerant Geometric Spanners
             Artur Czumaj and Hairong Zhao 
 
             Computing Homotopic Shortest Paths Efficiently
             Alon Efrat, Stephen Kobourov, and Anna Lubiw 
 
             Variants on Alternating Segment Paths
             Csaba D. T\'oth 

4:00-4:30    Break 

4:30-5:15    Contributed talks: 
 
             Optimal Motion Strategies to Track and Capture a Predictable Target
             Alon Efrat, H\'ector H. Gonzalez-Banos, Stephen G. Kobourov, 
               and Lingeshwaran Palaniappan 

             Online Dispersion Algorithms for Robot Swarms
             Esther M. Arkin, Michael A. Bender, S\'andor P. Fekete, 
               Tien-Ruey Hsiang, Nenad Jovanovic, Joseph S. B. Mitchell, 
               and Marcelo O. Sztainberg 
 
             New Approximation Results for the Maximum Scatter TSP
             Yi-Jen Chiang 

5:15-5:30    Minibreak 

5:30-6:30    Open Problem Session 

6:30         Dinner 

Friday, November 15

8:00-9:00    Continental Breakfast 

9:00-10:00   Contributed talks: 
 
             Constructing Hamiltonian Triangle Strips on Quadrilateral Meshes
             Gabriel Taubin 
 
             Interpolation over Light Fields with Applications in Computer Graphics
             F. Betul Atalay and David M. Mount 
 
             Visible Zone Maintenance for Real-Time Occlusion Culling
             Olaf Hall-Holt 

             Multi-way Space Partitioning Trees
             Christian A. Duncan 

10:00-10:30  Break 

10:30-11:20  Invited Talk: Lydia Kavraki (Rice)
             Modeling the Conformational Flexibility of Proteins

11:20-11:30  Minibreak 

11:30-12:30  Contributed talks: 
 
             Three Observations on Geometric Permutations
             Boris Aronov and Shakhar Smorodinsky 
 
             Cost Optimal Trees for Ray Shooting
             Herv\'e Br\"onnimann and Marc Glisse 
 
             The Min-Max Voronoi Diagram of Polygons and Applications
               in VLSI Manufacturing
             Evanthia Papadopoulou and D.T. Lee 

             Optimal Core-Sets for Balls
             Mihai B\u{a}doiu and Kenneth L. Clarkson 

12:30-2:00   Lunch 

2:00-2:50    Invited Talk: Piotr Indyk (MIT): 
             Approximate Algorithms for High-Dimensional Geometric Problems
	    The Slides from his talk are available.

2:50-3:00    Minibreak 

3:00-4:00    Contributed talks: 

             The Foldings of a Square to Convex Polyhedra
             Rebecca Alexander, Heather Dyson, Joseph O'Rourke 

             Tetris is Hard, Even to Approximate
             Erik Demaine, Susan Hohenberger, and David Liben-Nowell 

             Towards the Visualization of Overlapping Sets
             Xavier Boyen, Liadan O'Callaghan, and Nina Mishra 
 
             Can Polynomiography be Useful in Computational Geometry?
             Bahman Kalantari 

4:00-4:30    Break 

4:30-5:15    Contributed talks: 

             An Algorithm Oriented Mesh Database (AOMD) Application: Decimation
             B. Kaan Karamete 

             Hand Recognition Using Geometric Classifiers
             Yaroslav Bulatov, Sachin Jambawalikar, Piyush Kumar, and Saurabh Sethia 

             Sufficiently Fat Polyhedra are not 2-Castable
             David Bremner and Alexander Golynski 

5:15-5:30    Minibreak 

5:30-6:30    Open Problem Session