Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph

Hossein Boomari
  • Fonction : Auteur
  • PersonId : 1093215
Soheila Farokhi
  • Fonction : Auteur
  • PersonId : 1093216

Résumé

Visibility graph of a simple polygon is a graph with the same vertex set in which there is an edge between a pair of vertices if and only if the segment through them lies completely inside the polygon. Each pair of adjacent vertices on the boundary of the polygon are assumed to be visible. Therefore, the visibility graph of each polygon always contains its boundary edges. This implies that we have always a Hamiltonian cycle in a visibility graph which determines the order of vertices on the boundary of the corresponding polygon. In this paper, we propose a polynomial time algorithm for determining such a Hamiltonian cycle for a pseudo-triangle polygon from its visibility graph.
Fichier principal
Vignette du fichier
495613_1_En_5_Chapter.pdf (239.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03165378 , version 1 (10-03-2021)

Licence

Paternité

Identifiants

Citer

Hossein Boomari, Soheila Farokhi. Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph. 3rd International Conference on Topics in Theoretical Computer Science (TTCS), Jul 2020, Tehran, Iran. pp.61-71, ⟨10.1007/978-3-030-57852-7_5⟩. ⟨hal-03165378⟩
34 Consultations
13 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More