Fall Workshop

CRA-W/CDC Workshop

Full Proceedings

Fall Workshop on Computational Geometry (11/13-14)

Friday 11/13

9:00 Opening
1st session: Approximation (chair: Anna Lubiw):
9:05 Catalin Constantin, Shawn Brown, and Jack Snoeyink
Streaming Simplification of Labeled Meshes Using Quadric Error Metrics
9:20 David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu
A Practical Approximation Algorithm for the LTS Estimator
9:35 Leonidas Guibas, Nikola Milosavljević, and Arik Motskin
Connected Dominating Sets on Geometric Graphs with Mobile Nodes
9:50 Gary L. Miller, Todd Phillips, and Donald R. Sheehy
Approximating Voronoi Diagrams with Voronoi Diagrams
10:05 Dengpan Zhou and Jie Gao
Maintaining Approximate Minimum Steiner Tree and k-center for Mobile Agents in a Sensor Network
10:20 Break
2nd session: Invited Talk (chair: Jack Snoeyink):
10:35 Hanspeter Pfister (Harvard University)
The Connectome - Discovering the Wiring Diagram of the Brain
11:20 Break
3rd session: Representations, Data Structures, and Operators (chair: Godfried T. Toussaint):
11:35 Benoît Hudson
Succinct Representation of Well-Spaced Point Clouds
11:50 Sorelle A. Friedler and David M. Mount
Spatio-temporal Range Searching over Compressed Kinetic Sensor Data
12:05 Danny Z. Chen and Haitao Wang
Dynamic Data Structures for Simplicial Thickness Queries
12:20 Timothy M. Chan, David L. Millman, and Jack Snoeyink
Discrete Voronoi Diagrams and Post Office Query Structures without the InCircle Predicate
12:35 Short break
12:45 Lunch and Open Problems (chair: Joseph S.B. Mitchell)
13:35 Short break
4th session: Discrete Geometry (chair: Diane L. Souvaine):
13:45 Ronnie Barequet, Gill Barequet, and Günter Rote
Formulae and Growth Rates of High-Dimensional Polycubes
14:00 William Steiger, Mario Szegedy, and Jihui Zhao
Six-way Equipartitioning by Three Lines in the Plane
14:15 Mohammad Irfan, Justin Iwerks, Joondong Kim, and Joseph S.B. Mitchell
Guarding Polyominoes
14:30 Karin Arikushi and Csaba D. Tóth
Drawing Graphs with 90° Crossings and at Most 1 or 2 Bends per Edge
14:45 Javier Cano, Csaba D. Tóth, and Jorge Urrutia
A Tight Bound For Point Guards in Piece-Wise Convex Art Galleries
15:00 Break
5th session: Invited Talk (chair: Gill Barequet):
15:15 Dan A. Klain (University of Massachusetts Lowell)
If You Can Hide Behind It, Can You Hide Inside It?
16:00 Break
6th session: Mesh Generation and Sensor Networks (chair: Lenore J. Cowen):
16:15 Benoît Hudson, Gary L. Miller, Steve Y. Oudot, and Donald R. Sheehy
Mesh-Enhanced Persistent Homology
16:30 Gary L. Miller and Todd Phillips
Fast Meshing for Acute PLCs
16:45 Rik Sarkar, Wei Zeng, Xiaotian Yin, Jie Gao, Feng Luo, and Xianfeng Gu
Greedy Routing with Guaranteed Delivery Using Ricci Flows
17:00 Wei Zeng, Rik Sarkar, Feng Luo, Xianfeng Gu, and Jie Gao
Resilient Routing for Sensor Networks Using Hyperbolic Embedding of Universal Covering Space
17:15 Break
18:15 Reception at Hyatt Place

Saturday 11/14

7th session: Invited Talk (chair: Nancy M. Amato):
9:00 Chris Bishop (State Univ. of NY at Stony Brook)
Conformal Mapping in Linear Time
9:45 Break
8th session: Optimization (chair: Csaba D. Tóth):
10:00 Petter Brass
Computing the Largest Bounded Intersection of Halfspaces
10:15 Joseph S.B. Mitchell and Eli Packer
On Non-crossing (Projected) Spanning Trees of 3D Point Sets
10:30 Steven Bitner, Yam K. Cheung, Atlas F. Cook IV, Ovidiu Daescu, Anastasia Kurdia, and Carola Wenk
Visiting Points with a Bevel-Tip Needle
10:45 Esther M. Arkin, Irina Kostitsyna, Joseph S.B. Mitchell, Valentin Polishchuk, and Girishkumar R. Sabhnani
The Districting Problem
11:00 Steven Bitner, Yam-Ki Cheung, and Ovidiu Daescu
On the Minimum Color Separation Circle
11:15 Esther M. Arkin, Sándor P. Fekete, Joondong Kim, Joseph S.B. Mitchell, Girishkumar R. Sabhnani, and Jingyu Zou
The Pencil Packing Problem
11:30 Umut A. Acar, Benoît Hudson, and Duru Türkoglu
A Dynamic Algorithm for Well-Spaced Point Sets
11:45 Break
9th session: Invited Talk (chair: Joseph O'Rourke):
12:00 Brigitte Servatius (Worcester Polytechnic Institute)
k-Plane Matroids and Whiteley's Flatenning Conjectures
12:45 Lunch break
10th session: Metrics, Spaces, and Embeddings (chair: Esther M. Arkin):
14:00 Afra Zomorodian
Fast Construction of the Vietoris-Rips Complex
14:15 Atlas F. Cook IV, Jessica Sherette, and Carola Wenk
Computing the Fréchet Distance Between Polyhedral Surfaces with Acyclic Dual Graphs
14:30 Joondong Kim, Joseph S.B. Mitchell, and Jingyu Zou
Routing Parallel and Merging Lanes
14:45 Anand Kulkarni and Sandeep Koranne
The Gemcutting Approach to the Hirsch Conjecture (and Other Open Problems on Polytopal Graphs)
15:00 P. Thomas Fletcher, John Moeller, Jeff M. Phillips, and Suresh Venkatasubarmanian
Computing Hulls In Positive Definite Space
15:15 Break
11th session: Invited Talk (chair: Audrey Lee-St. John):
15:30 Kirk Haller (Dassault Systemes SolidWorks Corporation)
Computational Geometry Problems in CAD
16:15 Break
12th session: Graphics and Applications (chair: Joseph S.B. Mitchell):
16:30 Marta Fort, J. Antoni Sellarès, and Nacho Valladares
Reporting Flock Patterns via GPU
16:45 Shu Ye and Karen Daniels
Triangle-based Prism Mesh Generation on Interconnect Models for Electromagnetic Simulations
17:00 Sarang Joshi, Raj Varma Kommaraju, Jeff M. Phillips, and Suresh Venkatasubramanian
Matching Shapes Using the Current Distance
17:15 Christopher S. Stuetzle, Zhongxian Chen, Katrina Perez, Jared Gross, Barbara Cutler, W. Randolph Franklin, and Thomas Zimmie
Segmented Height Field and Smoothed Particle Hydrodynamics in Erosion Simulation
17:30 Sergey Bereg
Orthogonal Morphing of Orthogonal Drawings
17:45 Adjourn

CRA-W/CDC Workshop on Computational Geometry (11/15)

08:30 Gathering and registration
09:00 Joseph O'Rourke (Smith College)
Curve Shortening, Geodesics, and the Poincaré Conjecture [view abstract]
09:45 Godfried Toussaint (McGill Univ. and Harvard)
The Geometry of Musical Rhythm [view abstract]
10:30 Break
10:45 Anna Lubiw (Univ. of Waterloo and MIT)
Finding Shortest Paths [view abstract]
11:30 Jack Snoeyink (UNC Chapel Hill)
Exploring the Geometry of Molecular Interactions [view abstract]
12:15 Lunch break
13:15 Gill Barequet (Technion and Tufts University)
Half-a-Century of Counting Polycubes and Estimating their Growth Rate [view abstract]
14:00 Nancy M. Amato (Texas A&M University)
Randomized Motion Planning:
From Intelligent CAD to Group Behaviors to Protein Folding
[view abstract]
14:45 Break
15:00 Roberto Tamassia (Brown University)
Graph Drawing and Information Visualization [view abstract]
15:45 Matthew T. Dickerson (Middlebury College)
Understanding Voronoi Diagrams as Lower Envelopes [view abstract]
16:30 Break
16:45 Open-problems session
17:30 Adjourn