Matias Korman: Computing a visibility polygon using few variables

Abstract. We present several algorithms for computing the visibility polygon of a simple polygon P from a viewpoint inside the polygon, when the polygon resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O(nr) time, where r denotes the number of reflex vertices of P that are part of the output. The next two algorithms use O(log r) variables, and output the visibility polygon in O(n log r) randomized expected time or O(n log^2 r) deterministic time, where r is the number of reflex vertices of P.

Bodite pozorni, da se bo seminar začel ob 12:20.