Computing Visibility between moving Points

Abstract

We study the following problem. Let P be a simple polygon with n vertices and let B be a set of points moving along a linear path in P. In other words, the trajectory of an entity b ∈ B is a linear function [0, 1] → P. Given a query set R of linearly moving points in P, determine for each r ∈ R if it can see any entity b ∈ B. We propose a kinetic data structure to maintain the combinatorial structure of the union of visibility polygons. To capture the changes over time, we model the changes in the union as a three-dimensional structure, where the z-axis represents the time. We call this three-dimensional structure the Visibility Pillar VP. The visibility pillar is of size O(n^3m^3). On top of the union, we also maintain a vertical decomposition. Each time slice gives us an x-monotone subdivision in R^2. To detect and handle combinatorial changes, we use an event-driven approach, where our goal is to detect the critical times at which the union and the vertical decomposition changes combinatorially. Processing all combinatorial changes to VP takes O(n^3m^3 log(nm)) time, and it takes O(n^4m^4 log(nm)) time to process all combinatorial changes to the vertical decomposition. We then present an algorithm that tests if query entities see any entity b ∈ B. This algorithm uses the union boundaries and vertical decomposition boundaries to determine if a query entity crosses a trapezoid that is covered by the union at a given time, which takes O(|R|·max_{r∈R} Tr(n,m)·log(|R|+nm^2)+n^4m^4(log(|R|+nm^2)+log(nm)+k)) time execute, where Tr(n,m) is defined as the number of trapezoids a query entity r crosses over time. Since [1], solves a similar problem, i.e. point location in a three-dimensional cell complex, we adapted the approach discussed in the paper to our setting. We use their approach to build a dynamic point location structure to test if a query entity is contained in a trapezoid covered by the union at the time it appears for the first time. This also allows us to perform point location queries in the visibility pillar, where we can test if a query entity is visible at a given time. Performing such a query takes O(log^2(nm)) time.