# Herringbone partitions of regions and surfaces

Let $R \subset \mathbb{R}^2$ be a region of the plane bounded by a Jordan curve. The boundary $\partial R$ could be a polygon, or a smooth curve—there are variations depending upon boundary assumptions. I would like to partition $R$ into regions $R_i$ that can be striped by parallel lines with the property that each stripe meets the boundary $\partial R_i$ at an angle that excludes the open interval $(\frac{1}{4}\pi,\frac{3}{4}\pi)$. In other words, the stripes meet the boundary of $R_i$ at $45^\circ$ or more sharply; they cannot meet the boundary nearly orthogonally. (Here the boundary is the boundary of $R_i$, which might include portions of the boundary of $R$.) And the ultimate goal is to partition $R$ into the minimum number of such regions.

For example, a rectangle can be partitioned into one region, but it seems a circle may need four regions(?):

A number of questions suggest themselves:

Q1. For $R$ a polygon of $n$ vertices, what is the largest number of herringbone regions needed for a fixed $n$, and how many regions always suffice for a fixed $n$?

Q2. For $R$ a circle in $\mathbb{R}^2$, or the surface of a sphere in $\mathbb{R}^3$, what is the optimal (fewest regions) herringbone partition? Can the circle be herringbone-partitioned into fewer than four regions?

Q3. What is the optimal herringbone partition of a torus?

I'll stop here, as you can spin off these questions as easily as I. My original focus was on compact surfaces in $\mathbb{R}^3$ (the sphere and torus above), when the pattern is drawn by parallels to a geodesic, but it already seems interesting in $\mathbb{R}^2$. Thanks for any insights and/or pointers to relevant literature!

Update. Sergei's idea, as articulated by Cristi, leads to a 3-region herringbone partition of a circle. Here his Cristi's illustration from his comment:

-
I understand the question for flat surfaces, but what do you mean by parallel lines on the surface of a sphere or a more complicated curved surface? – John Pardon Sep 29 '12 at 22:56
@unknown: Good question! It is not so clear, is it? ... Let me tentatively stipulate: a geodesic and its parallels (which might not themselves be geodesics). Each "parallel" has a fixed distance separation from the generating geodesic. – Joseph O'Rourke Sep 29 '12 at 23:16
Should regions be connected? Convex? If not, you can merge two opposite quarters of the circle into one region. – Sergei Ivanov Sep 30 '12 at 11:28
You can merge two opposite quarters of the circle only by using zig-zags as in i.imgur.com/Z4yri.gif . This suggests the following fun but unhelpful trick. Any planar region as described can be approximated as good as we want by a region which can be covered by only one herringbone region. The approximation will be bounded by a curve made only of horizontal and vertical lines (i.imgur.com/GxJKw.gif) – Cristi Stoica Sep 30 '12 at 22:04
Isn't this question trivial for regions like the sphere which have no boundary? – Will Sawin Oct 1 '12 at 4:31

Three regions is the minimum for any convex figure with a smooth boundary. To construct a partition, let $AB$ be the diameter of $R$. The segment $[AB]$ splits $R$ into two pieces $R_1$ and $R_2$. Let $C_i$ be a point at maximal distance from $[AB]$ in $R_i$, $i=1,2$. Draw perpendiculars $C_iD_i$ from $C_i$ to $AB$. The segments $[AB]$, $[C_1D_1]$ and $[C_2D_2]$ split $R$ into 4 regions which can be filled by parallel lines just like the 4 quarters of the circle. Then you can merge two regions by removing the segment $[D_1D_2]$ or using a zig-zag if $D_1=D_2$.

Two regions are impossible. Indeed, parametrize $S^1$ by tangent directions of $\partial R$ (say, oriented counter-clockwise). For each region $R_i$, consider the set $R_i\cap\partial R$. The tangent directions of this set form angles at most $\pi/4$ with a fixed line, hence they belong to the union of two arcs of length $\pi/2$ in the circle of tangent directions. It is possible to divide $S^1$ into 2 pair of arcs like this, but then the two corresponding pairs of arcs in $\partial R$ cannot be connected by disjoint paths (I assume you don't want connected but not path-connected examples).

The same arguments, modulo minor details, works for any $n$-gon with angles sufficiently close to $\pi$. For example, for a regular $n$-gon with $n\ge 10$.

-

We can extend Sergei's answer to non-convex shapes.

If $n$ is the minimum number of arcs it takes to partition the boundary of the shape in a way such that the tangent angles for each arc lie in a union of two arcs of length $\pi/2$ in the circle of tangent directions, then it takes at least $n/2+1$ herringbone regions to partition the shape.

Proof: Consider the herringbone partition as a graph with vertices, edges, and faces. Its Euler characteristic must be $1$. Remove all leaves, then the Euler characteristic is

$|F|-\sum_{v\in V} \frac{d(v)-2}{2}$

where $d(v)$ is the degree of a vertex, and all summands are nonnegative.

All $n$ vertices on the boundary have degree $3$, so the number of faces is at least $n/2+1$.

Thus, a smooth curve that has a lot of Thurston-style corrugations can have an arbitrarily high lower bound on the number of regions needed.

-

Remarks:

1. This works as well for smooth figures, and for figures with corners, and polygons.

2. Different orientations of the diagonal lines may yield different number of pieces, so we should supplement this with a method of choosing the optimal direction.

-
I am not convinced this is optimal in general. Suppose I take one figure where a certain direction is optimal (and the difference between optimal and suboptimal is large), and another figure where a quite different direction is optimal (and the difference is again large) and connect them by a thin tube. It seems clear that the best way to cover this figure is with one region with the first direction, one region with the second direction, and a number of smaller regions. – Will Sawin Oct 3 '12 at 6:03
@Will Sawin: you're right, thanks. – Cristi Stoica Oct 3 '12 at 6:56