Local complexity measures for (simple) polygons

Abstract

There are various application areas that are considered important sources of the need to study visibility, the main ones are: robotics, geographic information systems (GIS) and computer graphics. Therefore, it is important to have efficient algorithms available to solve these problems. Many such algorithms are already presented in literature. Depending on the algorithm, the environment can be modeled in different ways, e.g. a terrain or a polygon. This project studies visibility inside of polygons, specifically simple polygons. A simple polygon is a polygon without holes and self-intersections.

It appears that the performance of these algorithms in practice is influenced by the polygons on which they are used. More specifically, their performance seems influenced by certain properties of a polygon. The project aims to gain insight in which properties can influence visibility computations for a simple polygon P. The first investigated polygon property is the size of the largest/average visibility polygon of P. The second property is the number of reflex vertices of P. The third property is the maximum/average number of vertices of P visible from a chord. An approximation of the chord property is also investigated. Here the maximum/average number of vertices visible from a diagonal is considered. The fourth and final property is a value that indicates how close P is to being a convex polygon.