On Stabbing and Visibility Graphs

Irena Pashchenko

An open problem was posed by Everett, et al., in 1996 [1]: does weak stabbing information determine the internal and external visibility graphs of a simple polygon? This information counts crossings of polygon edges with rays between vertices. The question is whether this distinguishes internal from external visibility edges. Although we have not completely settled this question, we can answer the question for "most" polygons, all those that do not contain a certain complex substructure. Our formal proof of this theorem is constructive, and leads to an algorithm which I implemented in a Java applet. This tool permits interactive testing of user-supplied polygons, such as that in Figure 1. Figure 2 shows that all the hundreds of visibility edges are correctly distinguished in this case.

I plan to continue working on this problem in the fall.*

 

Figure 1: Input Figure 2: Output

Advisor: Joseph O'Rourke

[1] H. Everett, F. Hurtado, M. Noy "Stabbing Information of a Simple Polygon," Proc. 8th Canad. Conf. Comput. Geom., Ottawa, pp. 74-79, 1996.


*Completed work: J. O'Rourke and Irena Pashchenko, "Zero-Parity Stabbing Information," Japan Conference on Discrete and Computational Geometry, Tokyo, Dec. 1998, pp. 93-97. ftp here