The Research On Algorithm To Solve LR-Visibility Problem In The Simple Polygon

LR-visibility problem is one of the most important problems of computational geometry. Researching on the character of LR-visibility polygon, it can help people develop the effective algorithm of these classic problems. Therefore, the research on the LR-visibility polygons has not only the theoretical significance, but also the practical value.Based on the characteristics of the simple polygons, this paper mainly research the character of LR-visibility polygon and whether the simple polygon is LR-visibility or not.Then, we give the necessary and sufficient conditions to determine whether a simple polygon is LR-visibility, and strictly prove it. In this paper, we give a simple, explicit characterization of LR-visibility polygons. It is obtained by mapping s structure of non-redundant components used in determining LR-visibility into a set of directed chords for a circle. Using our characterization, we further develop a simple O(n) time algorithm for computing the number of non-redundant component.Using this algorithm and the necessary and sufficient conditions to determine whether a simple polygon is LR-visibility, we can determine whether a given polygon is LR-visible in the liner time. This greatly simplifies the existed algorithms for determining whether a simple polygon is LR-visible and for reporting all pairs s and t which admit LR-visibility as well.In order to verify the feasibility and effectiveness of the algorithm, this paper compute the non-redundant component of the test date,and determine the LR-visible of the simple polygon, and show and analyze the running result of the algorithm.The results show that the algorithm is effective and practicable.