A Study Of The Algorithm For Recognizing Link-k LR-visibility Polygons

This paper mainly researches the problem of the link-k LR-visibility polygon identification.The research provides a basic condition for after researchers to give efficient solutions of some classical problems,such as the shortest watchman route problem.Therefore,the research for the link-k LR-visibility polygon is not only meaningful to theoretical studies,but also valued in practical applications.Based on the relative theories and concepts of simple polygon,this paper seeks some relative characteristics of link-k LR-visibility polygons and through these gives the solutions--link-k reflex vertexes,link-k ray-shootings,link-k components and non-redundant link-k components.The paper detailedly discusses the solving process and analysed the influencing factors of the non-redundant link-k components.According to the non-redundant link-k components,we give the necessary and sufficient conditions to determine whether a simple polygon is link-k LR-visible or not,and also give its strict proof by mapping the chord from non-redundant link-k components to round.By the necessary and sufficient conditions,when k=2,we give the detailed realization of this algorithm which determines a link-2 LR-visibility polygon.The algorithm can be extended to solve the problem of the link-k LR-visibility polygons,and detailed analyze the time complexity of this algorithm.According to the characteristics of the non-redundant components,this paper gives the algorithm to determine whether a simple polygon is link-k LR-visible in O(nlogn)time.