Splitting off from Splitline Algorithm for Redistricting.
Back in August 2010, I blogged about how Sandboxwalls could use the Splitline Algorithm to locate the starting seeds. I had hoped that someone would be upgrading the Splitline Algorithm software, or even better, that someone would help me create software that would locate the starting seeds for Sandboxwalls or Voronoi diagram redistricting. Splitline seems to have died. I have started once again to consider creating an algorithm to determine where to place the starting seeds. Splitline Algorithm nicely divides a state into areas, and one seed could be planted in the center of each area. Although I understand the basic concept of the Splitline Algorithm, I still don’t understand the details of how it should work.
Sandboxwalls will cut up a state into horizontal stripes. Each stripe is thick by the same amount of integer tenmillionths degrees of latitude. To initially split the state into two pieces, it is simple to start from the bottom of the State, move North and accumulate stripes into the newly created area until the desired population is exceeded. It is not difficult to start from the West and move a vertical line eastward until the desired population is reached in the newly created area west of the vertical line. The shorter of the horizontal line or vertical line can then be chosen to split the State into two areas. Splitline Algorithm would have chosen the shortest from among many dividing lines at many angles of slope instead of merely a pair.
I hope to justify this drastic simplification of Splitline by noting that I am just trying to locate the starting seeds instead of creating a final map. By using only horizontal and vertical dividing lines, the required software is greatly simplified. The resulting areas from a split would be convenient boxes instead of complicated polygons. After all, it seems that I will have to spend the time to create the software, and time is limited. I may need a new name for such a drastically degraded algorithm since it would not meet the specifications for Splitline.
Conceptually, the final split of a remaining area could be done by choosing from among more than just horizontal and vertical dividing lines. The vertical line could accumulate triangles instead of vertical stripes. The choice would be choosing between a triangle that increased the tilt of the dividing line or a triangle that decreased the tilt of the dividing line. Additionally, dividing lines could start with various angles of slope instead of merely horizontal and vertical. The question is whether this concept is worth extra time needed to write the extra FORTRAN, as well as the extra time spent by Sandboxwalls during execution.
Next blog, I will again examine computing the distance between points on the surface of planet earth. Perhaps I should have a robot write the software.