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

15th Annual Fall Workshop on Computational Geometry and Visualization

November 18-19, 2005

Amado Recital Room
Irvine Auditorium
Perelman Quadrangle
University of Pennsylvania
3417 Spruce Street
Philadelphia, PA 19104-6306 USA

Workshop Program

Important Note: Each talk is allocated a 15-minute time slot, with 13 minutes for actual presentation and 2 minutes for questions and change-over to the next talk. This schedule is packed tightly to accomodate many talks. It is important that speakers keep within their 13-minute limit in order to keep the conference program on track.

Friday, November 18, 2005

09:00	–	10:00	Session 1: 4 Talks [Session Chair: Shankar Krishnan] 09:00-09:15: Optimal Shape of a Blob. Carl M. Bender, Michael A. Bender. 09:15-09:30: Real-Time Kinetic Algorithms. Patchrawat Uthaisombut. 09:30-09:45: Iterated Snap Rounding with Bounded Drift. Eli Packer. 09:45-10:00: Frechet Distance between Simple Polygons. Kevin Buchin, Maike Buchin, Carola Wenk.
10:10	–	11:10	Session 2: 4 Talks [Session Chair: Ken Clarkson] 10:10-10:25: Depth Explorer: A Software Tool for Analysis of Depth Measures. J. Hugg, E. Rafalin, D. L. Souvaine. 10:25-10:40: Path Length in Proximity Graphs as a Data Depth Measure. Kathryn Seyboth, Eynat Rafalin, Diane Souvaine. 10:40-10:55: Travel Depth: A New Shape Descriptor for Macromolecules. Ryan G. Coleman, Kim A. Sharp. 10:55-11:10: Combining Discrete and Continuous Optimization to Detect Protein Substructure Similarity. L. Paul Chew.
11:30	–	12:30	Invited Talk: [Session Chair: Shankar Krishnan] Delaunay Meshing of Surfaces. Tamal Dey
13:45	–	14:45	Session 4: 4 Talks [Session Chair: John Iacono] 13:45-14:00: Enumerating Planar Minimally Rigid Graphs. David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa. 14:00-14:15: Local Overlaps in Unfoldings of Polyhedra. Anna Lubiw, Brendan Lucier. 14:15-14:30: Unfolding Well-Separated Orthotrees. Mirela Damian, Robin Flatland, Henk Meijer, and Joseph O'Rourke. 14:30-14:45: Flexibility of Subdivided Polyhedral Complexes. Audrey Lee, Ileana Streinu.
15:00	–	15:15	Remarks by NSF Program Director, Robert J. Grafton.
15:15	–	16:15	Invited Talk: [Session Chair: Suresh Venkatasubramanian] Time for Change: An Integrated Environment for Representation and Analysis of Complex Space-Time Processes. Donna J. Peuquet
16:20	–	17:50	Session 7: 6 Talks [Session Chair: Joe Mitchell] 16:20-16:35: Optimized Prediction for Geometry Compression of Triangle Meshes. Dan Chen, Yi-Jen Chiang, Nasir Memon, Xiaolin Wu. 16:35-16:50: Bounding the Number of Plane Graphs. Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, Birgit Vogtenhuber. 16:50-17:05: Dynamic Ham-Sandwich Cuts for Two Point Sets with Bounded Convex-Hull-Peeling Depth. M. A. Burr, J. Hugg, E. Rafalin, K. Seyboth, D. L. Souvaine. 17:05-17:20: Opposite-quadrant depth in the plane. Herv´e Br¨onnimann, J´anos Pach. 17:20-17:35: BSP Visibility on S2. John Fedorkiw, Sherif Ghali, and Todd Keeler. 17:35-17:50: The Complexity of Diffuse Reflections in a Simple Polygon. Boris Aronov, Alan R. Davis, John Iacono, Albert Siu Cheong Yu.

Saturday, November 18, 2005

09:00	–	10:00	Session 8: 4 Talks [Session Chair: Shankar Krishnan] 09:00-09:15: On Guarding and Partitioning Polygons. Yoav Amit, Joseph S. B. Mitchell, Eli Packer. 09:15-09:30: The Hunting of the Bump: On Maximizing Statistical Discrepancy. Deepak Agarwal, Jeff M. Phillips, Suresh Venkatasubramanian. 09:30-09:45: Sublinear Projective Clustering with Outliers. Nina Mishra, Rajeev Motwani, Sergei Vassilvitskii. 09:45-10:00: Bounded-velocity Approximations of the Mobile Euclidean 2-centre. Stephane Durocher, David Kirkpatrick.
10:10	–	11:10	Session 9: 4 Talks [Session Chair: John Iacono] 10:10-10:25: Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel Smid. 10:25-10:40: An Experimental Study of Weighted k-Link Shortest Path Algorithms. Ovidiu Daescu, Joseph S.B. Mitchell, Simeon Ntafos, James D. Palmer, Chee K. Yap. 10:40-10:55: Euclidean TSP on Two Polygons. Jeff Abrahamson, Ali Shokoufandeh. 10:55-11:10: THICK NON-CROSSING PATHS. Joseph S. B. Mitchell, Valentin Polishchuk.
11:30	–	12:30	Invited Talk: [Session Chair: Joe Mitchell] High-dimensional Convex Geometry, Metric Embeddings, and Graph Expansion. James R. Lee
13:45	–	14:45	Session 11: 4 Talks [Session Chair: Ileana Streinu] 13:45-14:00: Representing Topological Structures Using Cell-Chains. David E. Cardoze, Gary L. Miller, Todd Phillips. 14:00-14:15: Combinatorial and Algorithmic Applications of the Borsuk-Ulam Theorem. Sambudda Roy, William Steiger. 14:15-14:30: Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem. Jie Gao, Michael Langberg, Leonard J. Schulman. 14:30-14:45: Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-type Problems. Nir Halman.
15:00	–	16:00	Invited Talk: [Session Chair: Ileana Streinu] Predicting and Analzying Protein Interaction Networks. Mona Singh
16:20	–	17:35	Session 13: 5 Talks [Session Chair: Suresh Venkatasubramanian] 16:20-16:35: How to Water Carrots: Geometric Coverage Problems for Point Sets. Helmut Alt, Esther M. Arkin, Herve Br¨onnimann, Jeff Erickson, S´andor P. Fekete, Christian Knauer, Jonathan Lenchnerk, Joseph S. B. Mitchell, Sue Whitesides, Kim Whittlesey. 16:35-16:50: Efficient Algorithm for Approximating Maximum Inscribed Sphere in High Dimensional Polytope. Yulai Xie and Jinhui Xu. 16:50-17:05: On the Importance of Idempotence. Sunil Arya, Theocharis Malamatos, David M. Mount. 17:05-17:20: On the Equi-Area Partitioning Problem for Rectilinear Simple Polygons. Yiqing Wen, J. MacGregor Smith. 17:20-17:35: Recent Developments in NEARPT3 Nearest Point Query in E3 with a Uniform Grid. W. Randolph Franklin.