Pseudo-triangle visibility graph: characterization and reconstruction

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

71 viewed

Mehrpour, S

71 Viewed

Type of Document: Article
DOI: 10.24200/sci.2024.63200.8282
Publisher: 2024
Abstract:
The visibility graph of a simple polygon represents visibility relations between its vertices. Knowing the correct order of the vertices around the boundary of a polygon and its visibility graph, it is an open problem to locate the vertices in a plane such that it will be consistent with this visibility graph. This problem has been solved for special cases when we know that the target is a tower, a spiral, or an anchor polygon. Knowing that a given visibility graph belongs to a simple polygon with at most three concave chains on its boundary, a pseudo-triangle, we propose a linear-time algorithm for reconstructing one of its corresponding polygons. Moreover, we introduce a set of necessary and sufficient properties for characterizing visibility graphs of pseudo-triangles and propose polynomial algorithms for checking these properties. © 2024, Sharif University of Technology. All rights reserved
Keywords:
Computational geometry ; A-plane ; Characterizing visibility graph ; Graph characterizations ; Know-that ; Polygon reconstruction ; Property ; Pseudo-triangle ; Simple polygon ; Visibility graphs ; Algorithm ; Geometry ; Linearity ; Numerical model ; Polygon ; Reconstruction ; Visibility ; Graph algorithms
Source: Scientia Iranica ; Volume 31, Issue 21 , 2024 , Pages 1948-1962 ; 10263098 (ISSN)
URL: https://scientiairanica.sharif.edu/article_23594.html