Joint CS/Math Colloquium: Reconfiguring chains with discrete moves: flips and pops

October 21, 2016
4 - 5pm (tea at 3.30pm)
BP 101
Speaker: Perouz Taslakian, ROI
Host: Bruce Boghosian/Greg Aloupis

Abstract

Understanding motion has long been a central theme in both the theoretical and applied sciences. But even as our expanding knowledge of the mechanism in which objects move has led to developments in an array of applications, many basic questions remain unresolved.

In this talk, we will look into the mechanics of motion for polygonal chains and explore the question of whether it is possible to move between two different configurations of a given polygon using a predefined move. We frame our question as a problem in discrete geometry, whereby the moves we consider are a discrete sequence of steps. We will see that even when considering restricted moves applied to simple objects such as polygons, reconfiguration questions remain challenging.

In particular, we will talk about Erdos flips, and a more restricted version of such flips called pops. Given a polygonal chain that lies in the 2- dimensional plane, a pop reflects a vertex of this chain across the line through its two neighbouring vertices such that the resulting polygon lies in the same plane. We will see that using techniques from dynamical systems theory, we can show that for certain classes of polygons, the neighbourhood of any configuration that can be reached by smooth motion can also be reached by pops.

Bio: Perouz Taslakian received her PhD in computer science from McGill University in 2009 under the supervision of G. Toussaint and L. Devroye. She completed a postdoc at the Free University of Brussels, and has served as a faculty member and chair in the College of Science and Engineering at the American University of Armenia in Yerevan. Her areas of interest includes topics in discrete and computational geometry, in particular geometric chain reconfigurations and routing in geometric graphs.