Visibility Graphs of Anchor Polygons

Abstract : Visibility graph of a polygon corresponds to its internal diagonals and boundary edges. For each vertex on the boundary of the polygon, we have a vertex in this graph and if two vertices of the polygon see each other there is an edge between their corresponding vertices in the graph. Two vertices of a polygon see each other if and only if their connecting line segment completely lies inside the polygon. Recognizing visibility graphs is the problem of deciding whether there is a simple polygon whose visibility graph is isomorphic to a given graph. Another important problem is to reconstruct such a polygon if there is any. These are well-known and well-studied, but yet open problems in geometric graphs and computational geometry. However, these problems have been solved efficiently for special cases where the target polygon is known to be a tower or a spiral polygon. In this paper, we solve these recognizing and reconstruction problems for another type of polygons, named anchor polygons.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.72-89, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_6〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446265
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:50:58
Dernière modification le : vendredi 2 mars 2018 - 15:04:02
Document(s) archivé(s) le : mercredi 26 avril 2017 - 16:01:49

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Hossein Boomari, Alireza Zarei. Visibility Graphs of Anchor Polygons. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.72-89, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_6〉. 〈hal-01446265〉

Partager

Métriques

Consultations de la notice

63