Vertical Visibility among Parallel Polygons in Three Dimensions

Radoslav Fulek, Columbia University

February 24, 2015

Motivated by a paper of Babilon et al. entitled “Visibility Representations of Complete Graphs” we study the following problem. Let $C$ be a collection of homothetic copies of a convex k-gon P in the plane with the given stacking order. The collection $C$ forms a visibility clique if, for every pair of copies $P_1$ and $P_2$ in $C$, the intersection of $P_1$ and $P_2$ is not covered by the union of the copies in $C$ appearing between $P_1$ and $P_2$ in the stacking order.

We obtain an upper bound of $2^{2{k \choose 2}+2}$ on the size of a visibility clique of homothetic copies of a convex $k$-gon. In the case of translates of a regular convex $k$-gon we improve the bound to $O(k^4)$ thereby improving the upper bound of $2^{2^k}$ from the aforementioned paper.

Furthermore, we show that every visibility clique of $n$ translates of a regular k-gon contains a subset of size $cn^{1/6}$, for a fixed $c>0$, that is combinatorially equivalent to the best known lower bound construction, giving the bound of roughly $k/2$, for the visibility clique of homothetic copies of a convex $k$-gon. The last result holds in more general setting, where we consider pseudo-disc arrangements satisfying certain conditions instead of translates of a polygon.

Joint work (in progress) with Rados Radoicic.