Reasoning about visibility

We consider properties of sequences of spatial regions, as seen from a viewpoint. In particular, we concentrate on two types of regions: (1) general domains in which a region is any subset of the space, and (2) axis-parallel domains, where the regions are boxes in an N-dimensional space. We introduce binary relations allowing to express properties of these sequences and present two approaches to process them. First, we show that constraints on these relations can be solved in polynomial time for general domain and that the same problem is NP-complete in the axis-parallel case. Second, we introduce a modal logic on these relations, called Visibility Logic, and show that model-checking on a finite sequence of regions can be done in polynomial time (both in the general and axis-parallel cases). Finally, we present applications to image processing and firewall filtering.