Visibility Graphs of Staircase Polygons: Algorithm for Building Staircase Polygons from Slope-Ranking Balanced Tableaux

Visibility Graphs of Staircase Polygons: Algorithm for Building Staircase Polygons from Slope-Ranking Balanced Tableaux

Project Year: 2017
REU Student (s): Yulia Alexandr | Wesleyan University
Project Mentor (s) : James Abello - Computer Science
Project Abstract: There exists a relationship between staircase polygons, persistent graphs, and balanced tableaux. While many aspects of this relationship had been rigorously studied, the problem of recovering a simple staircase polygon whose visibility graph is isomorphic to the skeleton of a given slope-ranking balanced tableau remained open and was previously known to be PSPACE. In this paper, we demonstrate a deterministic polynomial-time algorithm for constructing a staircase polygon with desired properties and prove that certain conditions required by the algorithm hold for any balanced tableau.

REU