Download a PDF of the full set of abstracts

Download a PDF of the schedule only

## Friday October 31, 2014

### Thomas J. Dodd Center for Research

8:30-9:30 | Informal Socializing/Coffee |

9:30-10:45 | Contributed Talks 1 |

10:45-11:00 | Break |

11:00-12:00 | Invited Talk: Jon Bentley |

12:00-1:30 | Lunch (provided) |

1:30-2:45 | Contributed Talks 2 |

2:45-3:15 | Break |

3:15-4:30 | Contributed Talks 3 |

4:30-5:00 | Break |

5:00-6:30 | Contributed Talks 4 |

6:30pm | Dinner (not provided) |

## Saturday November 1, 2014

### Laurel Hall, Room 101

8:00-8:30 | Informal Socializing/Coffee |

8:30-9:30 | Contributed Talks 5 |

9:30-9:45 | Break |

9:45-10:45 | Contributed Talks 6 |

10:45-11:00 | Break |

11:00-12:00 | Invited Talk: Satyan Devadoss |

12:00-1:15 | Lunch (provided) |

1:15-2:30 | Contributed Talks 7 |

2:30-3:00 | Break |

3:00-4:30 | Contributed Talks 8 |

4:30 | Farewell |

## Contributed Talks 1 (9:30-10:45 Friday)

Mian Ahsan, Sachith Cheruvatur, __Moiri Gamboni__, Abhijai Garg, Oleg Grishin, Shintaro Hashimoto, Jermsak Jermsurawong, Godfried Toussaint and Lingliang Zhang

**A Simple Algorithm for Computing a Spiral Polygonization of a Finite Planar Set**

PDF

__Sarah Cannon__, Thomas G. Fai, Justin Iwerks, Undine Leopold and Christiane Schmidt

**NP-hardness of the minimum point and edge 2-transmitter cover problem**

PDF

__Hu Ding__ and Jinhui Xu

**FPTAS for Minimizing Earth Mover’s Distance under Rigid Transformations and Related Problems**

PDF

__Bahman Kalantari__

**Randomized Triangle Algorithms for Convex Hull Membership**

PDF

## Invited Talk: Jon Bentley (11:00-12:00 Friday)

### Selecting Data for Experiments: Past, Present and Future

This talk describes three different kinds of data that algorithm designers use to test their implementations.

Selecting input data for past problems typically involves scholarship to assemble existing data and ingenuity to model it efficiently.

Selecting data for present problems should be based on active discussions with users and careful study of existing data.

Selecting data to model problems that may arise in the future is the most interesting and delicate of the tasks that we will consider.

(This talk supplements an invited paper in the 2014 Symposium on Experimental Algorithms; it expands some of the stories in that paper, and tells one new story.)

## Contributed Talks 2 (1:30-2:45 Friday)

Arthur Befumo and __Jonathan Lenchner__

**Extensions of Golomb’s Tromino Theorem**

PDF

__Salles Viana Gomes de Magalhaes__, W. Randolph Franklin, Marcus V. A. Andrade and Wenli Li

**An efficient map generalization heuristic based on the Visvalingam-Whyatt algorithm**

PDF

__Bahman Kalantari__, Sharareh Alipour and Hamid Homapour

**Fast Approximation and Randomized Algorithms for Diameter**

PDF

Iffat Chowdhury and __Matt Gibson__

**Consistent Digital Line Segments in d Dimensions**

PDF

## Contributed Talks 3 (3:15-4:30 Friday)

Rom Aschner, __Gui Citovsky__ and Matthew Katz

**Exploiting Geometry in the SINRk Model**

PDF

__Anna Lubiw__ and Yizhe Zeng

**The Visibility Freeze-Tag Problem**

PDF

Gui Gitovsky, Kan Huang and Joseph Mitchell

**Optimally Routing a Tracker to Maximize the Total Time a Mobile Evader is in View**

PDF

__Wenli Li__, W. Randolph Franklin, Salles V. G. Magalhaes, and Marcus V. A. Andrade

**Restricted Bathymetric Tracklines Interpolation**

PDF

## Contributed Talks 4 Followed by Open Problem Session (5:00-6:30 Friday)

__Juan Pablo Yanez Puentes__ and Leonardo Solanilla Chavarro

**Elucidating Peirce Quincuncial Projection**

PDF

Hugo A. Akitaya, Erik D. Demaine and __Jason S. Ku__

**Simple Folding is Strongly NP-Complete**

PDF

## Contributed Talks 5 (8:30-9:30 Saturday)

Danny Z. Chen, __Ziyun Huang__, Yangwei Liu and Jinhui Xu

**On Clustering Induced Voronoi Diagrams**

PDF

__Huxley Bennett__, Evanthia Papadopoulou and Chee Yap

**A Subdivision Approach to Weighted Voronoi Diagrams**

PDF

Narendher Takkarsu, Ge Xia and __Binhai Zhu__

**Analysis of Lawson’s Oriented Walk in Regular and Random Delaunay Triangulations**

PDF

## Contributed Talks 6 (9:45-10:45 Saturday)

__Reed Williams__ and Horea Ilies

**Shape Analysis for Point Cloud Models**

PDF

Michael Burr and __David Letscher__

**Guaranteed Quality Approximations for Medial Axis of Implicit Planar Curves**

PDF

__John Bowers__

**Faster Reductions from Straight Skeletons to Motorcycle Graphs**

PDF

## Invited Talk: Satyan Devadoss (11:00-12:00 Saturday)

### Origami Folding and Evolutionary Trees

In the past 25 years, origami has seen a tremendous explosion, in the arts, the sciences, and in technology.

The mathematical theory of origami, in many ways, is at its infancy.

There is a simple relationship between origami folds and geometric trees, obtained simply by looking at the crease lines of a piece of folded polygonal paper.

In genetics, such trees play an important role in capturing the evolutionary process of species.

We try to show a natural map between these worlds, of spaces of polygons and spaces of metric trees, and ask some foundational questions about this map.

The heavy lifting of our work is done by an analogous version of a beautiful rigidity result of Cauchy from 1813.

## Contributed Talks 7 (1:15-2:30 Saturday)

__Morad Behandish__ and Horea Ilies

**On a Generic Shape Complementarity Score**

PDF

__Jiemin Zeng__, Joe Mitchell and Jie Gao

**The Data Gathering Problem for Sensors on a Line or a Tree**

PDF

Samuel Bald, __Matthew P. Johnson__ and Ou Liu

**Maximum Rectilinear Crossing Number**

PDF

__Philip Dasler__ and David Mount

**On the Complexity of an Unregulated Traffic Crossing**

PDF

## Contributed Talks 8 (3:00-4:30 Saturday)

Thiago Lemos, Suneeta Ramaswami and __Marcelo Siqueira__

**A Fast Algorithm for Computing Irreducible Triangulations of Closed Surfaces in E^d and Its Application to the TriQuad Problem**

PDF

Paul Alsing, Howard Blair, __Matthew Corne__, Gordon Jones, Warner Miller, Konstantin Mischaikow and Vidit Nanda

**Applications of Persistent Homology to Simplicial Ricci Flow**

PDF

__Salman Parsa__

**An Almost Optimal Algorithm for Dynamically Updating the Reeb Graph**

PDF

__Thomas Peters__, Kevin Marinelli, Eugene Kovalev, Kirk Jordan and Ji Li

**Computational Topology for Molecular Animation**

PDF

Elissa Ross, __Brigitte Servatius__ and Herman Servatius

**Geometric rigidity of graphs on the torus**

PDF