[EM] [ESF #420] Points, regions and contiguity

[Raph Frank]

Cross posting this.  Also, I think I have figured out the full set of
rules, at least for a convex shape.

On Sat, Nov 28, 2009 at 5:11 PM, Raph Frank <raphfrk at gmail.com> wrote:
> When trying to create districts out of blocks, ensuring contiguity
> adds an additional layer of complexity.
>
> The ideal situation would be if the blocks could be treated like
> points and a single line used to divide the blocks into 2 groups.
> There might be rules for other simple curves like arcs and parabolas,
> but no point in complicating things.

Each block counts as a vertex and it is connected by an edge to all
vertexes with which it has a boundary.

The rules are

- each vertex must

A)
be within the convex hull of the vertexes that it is connected to

or

B)
be on the convex hull of the entire shape, and be connected to the
previous and next vertexes on the boundary

Notes:

If a vertex is within the convex hull of its neighbours, then no 1
line can cut the connections to all of its neighbours.

If the vertex is on the convex hull and is connected to the next and
previous vertex, then no 1 line can cut connections to both of those
vertexes, unless the line separates the vertex from all the other
vertexes (so still technically produces 2 contiguous regions).

A vertex that breaks the above rules could be fixed, by combining it
with a neighbour.  For example, on:

www.electionsciencefoundation.com/temp_images/convex_vertex.png

The red vertexes break the rules.

Each one is removed and the red lines indicate the new boundary.

The effect is to make the concave part of the boundary strictly concave.

Also, unless the line cuts the actual boundary, it cannot cut the
vertex based boundary.