Stabbing information of a simple polygon

The purpose of this paper is to investigate a new combinatorial object desc ribing the structure of a simple polygon and compare it to other well-known objects such as the internal and external visibility graphs, the convex hu ll and the order type of the vertex set. We call the new object the stabbin g information. In fact, we define three variations of the stabbing informat ion, strong, weak and labelled, and explore the relationships among them. T he main result of the paper is that strong stabbing information is sufficie nt to recover the convex hull, the internal and external visibility graphs and to determine which vertices are reflex and it is not sufficient to reco ver the order type of the vertex set. We also show that the labelled stabbi ng information is equivalent to the order type. We give algorithms for comp uting each of these new structures. (C) 1999 Elsevier Science B.V. All righ ts reserved.