Update 1 (March 18, 2021): I won the “Best Student Paper Presentation” at CALDAM 2021 for this work! I have also been invited to submit an extended version of the paper to DAM.
Update 2 (August 1, 2021): A journal version of this paper is under review. Here is the corresponding blog post.
In one of my previous posts, I had described the Discrete Terrain Guarding problem. Quickly, the problem is to place guards on the vertices of a \(x\)-monotone polygonal chain such that each vertex of that chain is seen by one of these guards. This problem turns out to be NP-Hard but admits a PTAS. A major open question is whether or not this problem is FPT with respect to the size of the guard set.
It was proved in 2018 by Ashok et al. that a restriction of this problem (where the edges describing the terrain are parallel to one of the axes) is indeed FPT with respect to the solution size. One of the results that they used to design their algorithm was the following: if there exists a set of vertices \(U\) of the terrain which cannot be seen by \(k\)-many guards, there exists a \(U’ \subseteq U\) of size \(k+1\) that cannot be seen by \(k\)-many guards. This result followed, as a corollary, from a lemma proved by Katz and Roisman which established a relationship between the Orthogonal Terrain Guarding problem and the Clique Cover problem in chordal graphs.
My paper (DOI) extends the result proved by Katz and Roisman to all terrains and thus extends the corollary given by Ashok et al. to general terrains. This is done by an extensive use of the Order Claim, first stated by Ben-Moshe et al. in 2007, on the various cases that pop up depending on the positions of the guards and the vertices that they are guarding. It will be interesting to see if this can be used to prove (or disprove) that Terrain Guarding is FPT.
This is my first academic publication! This paper is a result of my COVID-induced-6-month-long break. I presented this paper at CALDAM-2021. Unfortunately, this was done from my hostel room in NISER (during end-semester exam week, sigh) and not in the foothills of the Shivaliks at IIT-Ropar due to the pandemic. Since this was a solo paper, it was extremely demanding - especially since my manuscript came back for corrections during the busiest part of my semester. I made a lot of mistakes and thus learnt a truckload. A huge thanks to my mentor Dr. Aritra Banik for initial discussions and support during the final stages!
Feel free to email me if you want to discuss this topic! The pre-print of this paper can be downloaded as a PDF from here: