University of Connecticut University of UC Title Fallback Connecticut

Program

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