|
|
| Figure 1: Input | Figure 2: Output |
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.