A Decomposition Theorem for Simply Connected Orthogonal Polygons

Abstract

Let \(S\) be a simply connected orthogonal polygon in the plane. Assume that the vertex set of \(S\) may be partitioned into sets \(A, B\) such that for every pair \(x, y\) in \(A\) (in \(B\)), \(S\) contains a staircase path from \(x\) to \(y\). Then \(S\) is a union of two or three orthogonally convex sets. If \(S\) is star-shaped via staircase paths, the number two is best, while the number three is best otherwise. Moreover, the simple connectedness requirement cannot be removed. An example shows that the segment visibility analogue of this result is false.