ICS Theory Group

ICS 269, Spring 2002: Theory Seminar

24 May 2002:
Title: Visibility Queries and Maintenance in Simple Polygons, by B. Aronov, L.J. Guibas, M. Teichmann, and L. Zhang, Discrete & Computational Geometry Vol. 27, 2002, pp.461-483. (Preliminary version in Lecture Notes in CS, 1533, pp. 357-367, 1998.)
Speaker: Javid Huseynov

Abstract: The authors explore novel aspects of visibility for stationary and moving points inside a simple polygon P. They provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This results in a query time proportional to the size of visibility polygon but without cubic space overhead of earlier methods.

By exploring the connection between visibility polygons and shortest-path trees, the authors obtained a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside a simple polygon. The combination of the static and kinetic algorithms leads to a new static algorithm in which the authors trade off space for increased overhead in the query time.