- 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
- Student 1 Institution:
Wesleyan University
- Project Mentor:
James Abello
- Project Mentor Area:
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.
