Characterizing certain staircase convex sets in $\R^d$

Marilyn Breen

Abstract: Let $\C = \{C_1, \ldots, C_n \}$ be a family of distinct boxes in $\R^d$ whose intersection graph is a tree, and let $S = C_1 \cup \cdots \cup C_n$. Let $T \subseteq S$. The set $T$ lies in a staircase convex subset of $S$ if and only if for every $a, b$ in $T$ there is an $a-b$ staircase path in $S$. This result, in turn, yields necessary and sufficient conditions for $S$ to be a union of $k$ staircase convex sets, $k \geq 1$. Analogous results characterize $S$ as a union of $k$ staircase starshaped sets. Further, when $d \geq 3$, the set $S$ above will be staircase convex if and only if for every chain $A$ of boxes in $\C$, each projection of $A$ into a coordinate hyperplane is staircase convex. Finally, if $S$ is any orthogonal polytope in $\R^d$, $d \geq 2$, $S$ is staircase convex if and only if, for every $j$-flat $F$ parallel to a coordinate flat, $F \cap S$ is connected, $1 \leq j \leq d - 1$.

Keywords: orthogonal polytopes, staircase convex sets, staircase starshaped sets

Classification (MSC2000): 52.A30, 52.A35

Full text of the article:

• Compressed PostScript file (384 kilobytes)
• PDF file (156 kilobytes)