Recovering Graphs from Their Witness Unit Square Representation

Witness representations of graphs are a variant of geometric intersection representations of graphs, where we are given a set of convex objects and a set of points (witnesses). Every vertex is represented by one object and two vertices are connected if they intersect and their intersection contains no witness. Given a witness representation of $n$ objects and $m$ witnesses, we want to compute (recover) the graph it represents. Explicitly computing the intersection graph of all $n$ objects which intersect at most $k\in O(n^2)$ times and checking for every intersection if it contains a witness requires $O(n^2\cdot m)$ time. If the intersection graph is sparse, then the runtime can be reduced to $O(n\log m)$. However if there are $O(n^2)$ intersections between objects but the witness intersection graph has only $k\in O(n)$ edges, the naïve method would still require $O(n^2\cdot m)$ time. Our goal is to reduce this to $\tilde{O}(n+m+k)$ by using an output sensitive algorithm. Towards this goal, we consider here the square version.

A witness unit square representation (wUSR) – also shown in Figure 1(a)) – is a tuple $(𝒮,𝒲)$ where $𝒮$ is a set of $n$ axis-aligned unit squares and $𝒲$ is a set of $m$ point features (witnesses). The witness unit square graph $G(R)=\{𝒮,E\}$ is shown in Figure 1(b)). If $\{S_i,S_j\}$ intersect and their intersection contains a witness $W$, the edge $\{S_i,S_j\}$ is blocked by $W$.

To solve the problem we consider the dual of the representation, which represents any square in $𝒮$ with its center point and every witness with a unit square centered at the witness (Figure 1(c)). The large square $B_i$ of $S$ is a square of side length 2 centered at $P_i$.

Intuitively the previous observations state that everything relevant for a dual point of a square $S$ is contained in its large square. We assume general position. The edges of $G(R)$ are partitioned into a set with positive slope (right edges) and negative slope (left edges). For the remainder of this paper we focus on right edges; left edges are handled symmetrically.

Consider the top-right quadrant $B^{\nearrow }$ of a large square $B$ of $S$. For every right edge $\{S,S^{\prime }\}$, with $S$ lower than $S^{\prime }$, the dual point $P^{\prime }$ of $S^{\prime }$ is in $B^{\nearrow }$. For every witness $W$ that is contained within $S$, we know by Observation 3 that it’s dual square $Z\subset B$ and in particular the top-right corner of $Z$ is contained in $B^{\nearrow }$. Let $𝒯$ be the set of top-right corners of witness dual squares that are contained in $B^{\nearrow }$. We say a point $A\in B^{\nearrow }$ dominates a point $A^{\prime }\in B^{\nearrow }$ if $A$ is higher and further right than $A^{\prime }$.

We build a two dimensional range tree on all points in the set $𝒫$, i.e., all dual points of squares in $𝒮$. Every secondary level node $N$ corresponds to some region $R_N$, a (canonical) subset of points $P_N\subseteq 𝒫$, and a subset $T_N\subseteq 𝒯$. We order $T_N$ to form a staircase. Let $P_N^{\prime }$ be the subset of $P_N$ not dominated by a point in $T_N$, i.e. $P_N^{\prime }$ is the subset above the staircase. We store $P_N^{\prime }$ in a priority search tree [1] enabling efficient reporting of all points in $P_N^{\prime }$, above and to the right of a query point. This can be done in $O((n+m)\log (n+m))$ time

For every point $P_i\in 𝒫$ of a square $S_i\in 𝒮$, we query this data-structure with a search window corresponding to $B_i^{\nearrow }$ of the large square of $S_i$ in $O({\log }^{2}n)$.The query will report a number of subsets of $𝒫$. The returned sets can be interpreted as a partition of the search quadrant into columns, which are again subdivided into rows (forming cells); see Figure 2. The cells are processed column by column, right to left and top to bottom within a column. When processing these cells, we track $\widehat{x}$ and $\widehat{y}$, i.e., the highest $x$ and $y$ coordinates over all staircases and report the canonical subsets without points dominated by $(\widehat{x},\widehat{y})$. Four cases of previous staircase encounters are distinguished (none, previously this column, previously in earlier column, previously this and earlier column); we refer again to Figure 2.

The last case (at most once per column, i.e., $O(\log n)$ times) requires an additional query in the priority search tree. Since the query square is subdivided into at most $O({\log }^{2}n)$ cells – let $𝒞$ be the set of all cells – in the query result of the range query, the entire time requirement for a single query plus processing of the cells is

since ${\sum }_{C\in 𝒞}{k}_C=k_i$, the number of reported edges. We need one query per dual point of a square in $S$ and correctly compute all $k$ right edges in time $O(n{\log }^2(n+m)+{\sum }_{i=1}^n{k}_i)$.