Constant-Workspace Algorithms for Visibility Problems in the Plane
Mikkel Abrahamsen · 2013
In the constant-workspace model, the input is given as a read-only array which allows random access and the output is to be produced on a write-only array as a stream. In addition to that, only a constant number of variables are available, independent on the size of the input. Most ordinary algorithms for geometric problems make heavy use on the construction of smart data structures such as doubly-linked lists, heaps, and search trees which enable fast processing. In the constant-workspace model such data structures are not available due to the small amount of memory. Instead we need to access the input repeatedly. We try to minimize the number of accesses in order to make the algorithms as efficient as possible. In this thesis, we present new algorithms for visibility problems in the plane using constant workspace. We devise an O(n2)-time algorithm computing the circular visibility region of a polygon with n vertices from a given point within the polygon. Next, we present an O(n)-time algorithm to compute the visible part of one edge from another edge in a polygon. Using that algorithm, we describe an algorithm