DIMACS
DIMACS REU 2017

General Information

Mountain View
Student: Yulia Alexandr
Office: CoRE 450
School: Wesleyan University
E-mail: yalexandr@wesleyan.edu
Project: Visibility Graphs of Staircase Polygons

Project Description

For any balanced tableau, using the local maxima (minima) rule described by Abello et al, we can obtain a matrix of zeros and ones, which corresponds to the adjacency matrix of some graph. Given a balanced tableau, we want to be able to construct a staircase polygon whose visibility graph is isomorphic to the local maxima graph of the tableau given. The problem is known to be PSPACE, yet we also want to know whether it is NP or P. (More details/terminology are given in the presentation as well as the reference paper below).

Weekly Log

Week 1:
This week, we got introduced to the program. I met with my mentor, Prof. Abello, on the first day and he explained to me in great detail the problem I'll be working on referring to his paper, which I had read before we met. He answered my questions and gave me several suggestions as to how we could approach the problem. The project seemed very interesting, so I began to prepare my presentation and consider some special cases/examples. I also downloaded and began to explore graph theoretical tools in Mathematica.
Prof. Abello looked at my PPT presentation when it was done, approved it, and gave me several useful suggestions. He also gave me the paper of the REU student who worked on a related problem during one of the previous summer REUs, and I believe this can be very helpful in terms of gaining more intuition about the problem. I spent Friday reading and analyzing the paper.
We also got to create our own webpage using HTML. It was a good experience, because I've never created a webpage before. Overall, the first week was very interesting, and I hope the rest of the summer will be productive and fun!
Week 2:
We gave our presentations on Monday, and it went very well. I started working on the convex hull and induction approaches Prof. Abello and I discussed, applying it to many special cases on 4, 5, 6, 7, 8, and 9 vertices. I got some results for decomposable graphs, but after I met with my mentor, he told me that I should be looking at non-decomposable examples, since those are the tricky ones. He also shared some very useful insights regarding the induction approach. So I generated more such examples and started working with them. I also read the previous year's student's paper and considered the example on which his algorithm failed, because that could give us more intuition and suggest more different approaches to try. On Friday I came up with an idea which I need to explore and test further and discuss with my mentor next week. Overall, I find the problem I'm working on very interesting and the fact it's been open for over 22 years makes it even more exciting.
I also began to learn Python in my free time, because I want to be able to code some ideas later and test them, and since my mentor gave me some existing code in Python, it will be easier to just add up to it.
Week 3:
This week, I have been developing and testing the appoach that looked very promising, but ran into an issue. My mentor and I shared some thoughts about how we could fix it, and he suggested that this approach could work under certain assumptions. The approach I am describing takes advantage of unboundedness while constructing visibility regions and attempting to preserve slope rankings. The problem lies in the fact that we do not necessarily know that the visibility region of some point in the specific polygon we're constructing is non-empty. In fact, there exist examples where it can be empty. Yet, intuition and examples we looked at suggest that there should exist another isomorphic polygon where the region in question is not empty. However, we have not suceeded in proving that such a polygon exists yet. I attempted to prove it by taking advantage of inverse completeness of every localmax graph (details omitted), however, there are some caviats I did not take into account. During our meeting on Friday, Prof. Abello suggested that maybe we should try preserving the ranking of only some slopes, where it is necessary, and not all of them (details omitted). I will work on develping this approach further next week.
Week 4:
This week, I was trying to find an example of a tableau that has a polygon that produces an empty visibility region for one of its vertices. Prof. Abello told me that such examples exist, but they are very complicated. After many unsuccessful attemps I gave up and started working with an abstraction of such a case. I attempted to consider (presumably) all possible constructions that can cause an empty region, but quite surprisingly I ended up proving that all of them lead to some sort of contradiction and hence aren't possible. If the proof were correct, this would mean empty regions aren't possible at all, yet I am pretty sure I am missing cases in that proof or some of my assumptions are incorrect, since my mentor said they do exist.
In theory, the possibility of empty regions is where our potential algorithm breaks. This is why I am trying to gain some intuition regarging how they are formed so we could somehow change a polygon (without changing its visibility graph) to make the region in question non-empty. This would simply modify our algorithm by adding the case that handles empty regions. Yet, so far, we don't know how exactly to take care of empty regions (or even what they can look like).
Finally, I found an interesting example with a fully bounded visibility region. However, all attempts of making it empty or restricting it further weren't successful.
Week 5:
Progress! I was able to prove that empty regions are not possible as long as we preserve slope ranks of farthest seen vertices of each vertex at every stage of construction. As part of the proof, I also showed that any potential empty region formed by k lines can be reduced to that formed by 2 contradictory lines. All that's left to show in order for the algorithm to work is that we are able to preserve slope ranks of all the entries in the nth row of the tableau that correspond to 1-entries in the localmax graph (induction). We believe this conjecture to be true, though proving so appears to be very challenging. Even though we already know (from our inductive hypothesis) that we always have some visibility region for n, we do not necessarily know the slope ranking of all 1-enties can be preserved for some point in that region.
Preserving slope ranks often restricts visibility regions significantly (as we draw already known slope rays in-between which the new point must reside), yet we want to prove the restricted region is never empty. (Just to clarify, we try to preserve relative slope ranks, not actual slopes!) I have been having a really (really!) hard time trying to prove this, and so far it hasn't been successful. On Thursday, Prof. Abello suggested to look at visibility graphs as special trees, and maybe this would give us more intuition as to how to proceed with the proof.
On Friday we went to IBM, and it was a really fun trip!
Week 6:
I proved that slope ranks of all 1-enties in the nth row can always be preserved for some point in a visibility region. It is an inductive proof with 4 cases all of which lead to some kind of contradiction and thus it shows that restricted visibility regions are never empty. If all the proofs are correct (which Prof. Abello will check and discuss with me), this would mean our algorithm is correct.
In addition to the above results, we proved that, using the algorithm, empty visibility regions are not possible for concave-concave and concave-convex paths (and hence convex-convex and convex-concave by symmentry) independently of the general case. Prof. Abello also told me to try proving the general case using reversible entries (can be found in his paper) and symmentry with concave-concave paths because this proof may be neater than the one I have (messy case analysis) and because we want to make sure that our result is correct. I wrote a proof and I am not quite convinced myself, so I am waiting for Prof. Abello's feedback on that.
On Friday, Prof. Abello and I discussed our future plans. We plan on finalizing write-ups, etc. in August and September via Skype and email to prepare for a potential publication. My final report that is due soon will supposedly be the first draft of the paper (with some additional intermediate results, etc).
Week 7:
I was able to construct a proof for the general case using reversible entries approach (though it seems a little unconvincing) and waiting for Prof. Abello's feedback on it. It seems to be a much neater proof than the one we had before (messy case analysis).
I also worked on my final presentation and presented on Friday.
Week 8:
This week we arrived to Prague and started attending lectures. The lectures are extremely interesting and I enjoy them very much! We did some sightseeing with the Czech collegues (who are very welcoming) and went on a trip to Cesky Krumlov with them (which was a lot of fun). I also worked on my report that is due next week.
Week 9:
This week we attended more [cool] lectures at Charles University and went hiking. We also started working on transcribing one of the lectures from the conference. I finished and submitted my final report.

References

[1] Abello et al, Visibility Graphs of Staircase Polygons and the Weak Bruhat Order, I: from Visibility Graphs to Maximal Chains*. Discrete & Computational Geometry. 1995. 331-358.

Presentations


Additional Information