Constant-Workspace Algorithms for Visibility Problems in the Plane
Item is


Abrahamsen, Mikkel1, Forfatter
Katajainen, Jyrki2, Vejleder
1Det Naturvidenskabelige Fakultet, Københavns Universitet, København, Danmark, diskurs:7010              
2Datalogisk Institut, Det Naturvidenskabelige Fakultet, Københavns Universitet, København, Danmark, diskurs:7022              
skjul Ophav
Vis Ophav


Ukontrollerede emneord: Algorithm, optimal algorithm, computational geometry, constant workspace, visibility
 Abstract: 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
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
computing the weak visibility polygon from a segment in O(mn) time, where m is
the number of vertices of the weak visibility polygon. Finally, we show how the
computation of weak visibility polygons makes it possible to compute a minimum
link path between two points in a polygon in O(n2) time.
skjul Indhold
Vis Indhold


visibility.pdf (Hovedtekst)
Mime-type / størrelse:
application/pdf / 727KB
Copyright dato:
Copyright information:
De fulde rettigheder til dette materiale tilhører forfatteren.
skjul Filer
Vis Filer


Bogmærk denne post:
 Type: Speciale
skjul Basal
Vis Basal


Vis Links


Sprog: English - eng
 Datoer: 2013-06-12
 Sider: -
 Publiceringsinfo: København : Københavns Universitet
 Indholdsfortegnelse: -
 Note: -
 Type: Speciale
skjul Detaljer
Vis Detaljer


Vis Kilde