Stabbing information of a simple polygon

Hazel Everett 1 Ferran Hurtado 2 Marc Noy 2
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The purpose of this paper is to investigate a new combinatorial object describing the structure of a simple polygon and compare it to other well-known objects such as the internal and external visibility graphs, the convex hull and the order type of the vertex set. We call the new object the stabbing information. In fact, we define three variations of the stabbing information, strong, weak and labelled, and explore the relationships among them. The main result of the paper is that strong stabbing information is sufficient to recover the convex hull, the internal and external visibility graphs and to determine which vertices are reflex and it is not sufficient to recover the order type of the vertex set. We also show that the labelled stabbing information is equivalent to the order type. We give algorithms for computing each of these new structures.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 1999, 91 (1-3), pp.67-92
Liste complète des métadonnées

https://hal.inria.fr/inria-00098848
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:13
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00098848, version 1

Collections

Citation

Hazel Everett, Ferran Hurtado, Marc Noy. Stabbing information of a simple polygon. Discrete Applied Mathematics, Elsevier, 1999, 91 (1-3), pp.67-92. 〈inria-00098848〉

Partager

Métriques

Consultations de la notice

161