Dividing an octahedron into two congruent regions 
Consider a regular solid octahedron, which includes the interior.  Let $r$ be the subset consisting of the top vertex,  two vertices adjacent to it but not to each other, and the two edges between them, as in the diagram above.  Let $g$ be the congruent subset constructed on the two edges and three vertices that do not intersect $r$.
Now color every point of the octahedron red if it is closer to some point of $r$ than to any point of $g$, and conversely green if it is closer to $g$ than to $r$.  We can call the sets of red and green points $R$ and $G$; by symmetry, they are congruent.  The boundary between them is the (two-dimensional) set $B$ of all points equidistant from $r$ and $g$.

What does $R$ look like?  What shape is the boundary $B$?

It appears to me that the intersection of $B$ and the surface of the octahedron is a wiggly, approximately cubical loop made from eight parabolic segments joined end to end to end, but I am not certain.  
It also seems plausible that $B$ is obtained from this wiggly loop by taking the union of the straight segments from the points of the loop to the center $O$ of the octahedron, but again I am not sure.
In any case I am not able to visualize what this actually looks like or what the congruent solids $R$ and $G$ look like.
 A: The locus of the boundary between the two regions within the octahedron is given by the condition $$\frac{1}{2}(-x^2+y^2-4z) + (z-1)|x| + (z+1)|y| = 0, \quad |x| + |y| + |z| \le 1.$$  As already pointed out, this is the union of four sections of hyperbolic paraboloids.  See the animation:

Consider the octahedron with vertices $$(\pm 1, 0, 0), (0, \pm 1, 0), (0, 0, \pm 1)$$ in $\mathbb R^3$, and, because of the reflection symmetry, consider the quadrant where $x, y \ge 0$.  Without loss of generality, suppose the red line is parametrized by $$R(t) : [0,1] \mapsto \mathbb R^3, \quad R(t) = (1-t)(0,1,0) + t(0,0,1) = (0, 1-t, t)$$ and the green line by $$G(u) : [0,1] \mapsto \mathbb R^3, \quad G(u) = (1-u)(1,0,0) + u(0,0,-1) = (1-u, 0, -u).$$  Then for a point $(x,y,z)$ on the boundary, the minimum distance to each line satisfies the condition $$\min_{u \in [0,1]} |G(u) - (x,y,z)| = \min_{t \in [0,1]} |R(t) - (x,y,z)|.$$  To this end, we have
$$|R(t)-(x,y,z)|^2 = x^2 + (t+y-1)^2 + (t-z)^2, \\ 0 = \frac{d}{dt}\left[|R(t) - (x,y,z)|^2\right]  \Rightarrow t = \frac{1-y+z}{2}.$$  Similarly, $$u = \frac{1-x-z}{2}.$$  Then solving the equality condition gives $$2x^2 + (y+z-1)^2 = 2y^2 + (x-z-1)^2.$$  This already implicitly defines the boundary in the given quadrant; so if we replace $(x,y,z)$ by $(|x|,|y|,z)$, we get the above relationship.  We can also write it as $$z = \frac{x^2-y^2 + 2|x| - 2|y|}{2(2-|x|-|y|)}.$$
A: The boundary is defined by the set of points equidistant from the two closest line segments.  
For each red/green pair (4 pairs), that set of points is a hyperbolic paraboloiod.
