李银杰小组第一次讨论论文.doc

Summary Gerrymandering, the practice of dividing political districts into winding and unfair geometries, has a deleterious effect on democratic accountability and participation. Incumbent politicians have an incentive to create districts to their advantage (California in 2000, Texas in 2003); so one proposed remedy for gerrymandering is to adopt an objective, possibly computerized, methodology for districting. We present two efficient algorithms for solving the districting problem by modeling it as a Markov decision process that rewards traditional measures of district “goodness”: equality of population, continuity, preservation of county lines, and compactness of shape. Our Electoral District-dividing Model basing on the voronoi picture simulates the creation of a xed number of districts for an arbitrary geography for districts and specifying particular growth rules. The result of this process is refined in our Partition Optimization Model, which uses stochastic domain hill-climbing to make small changes in district lines to improve goodness. We include as an extension an optimization to minimize projected inequality in district populations between redistrictings. As a case study, we implement our models to create an unbiased, geographically simple districting of New York using tract-level data from the 2000 Census.What is Gerrymandering? Gerrymandering is division of an area into political districts that give advantage to one group. Frequently, this involves concentrating “unfavorable” voters in a few districts to ensure that “favorable” voters will win in many more districts. To squeeze unfavorable voters into a few districts, gerrymandering creates snaky and odd shaped regions. The eponymous label was created when politician Elbridge Gerry pioneered this technique in early 19th century and his opponents claimed that the districts resembled salamanders.Basic Terminology Packing: Forcing a disproportionately high concentration of a particular group into one district to lessen their impact in nearby districts. Cracking: Spreading members of a group into several districts to reduce their impact in each of these districts. Forfeit district: A district where group A packs the members of group B so that group B wins this district but loses several surrounding districts that B might win with a different districting scheme. Wasted Vote: A vote cast by a member of group A in a district where A is already assured victory, so voting has no bearing on the result. In general, the group with more wasted votes is made worse off by a districting plan. Why Is It So Bad? Gerrymandering reduces electoral competition within districts, since cracking/packing makes elections uncompetitive. Further, incumbent representatives are in no real danger of losing elections, so they do not campaign vigorously, which can lead to lower voter turnout. Exacerbating the problem, incumbents increased advantage means that they have less incentive to govern based on their constituents interests, so democratic accountability and engagement mutually deteriorate.Gerrymandering also presents the practical problem that it is diffcult to explain to voters why district shapes are so labyrinthine. Some districts connect demographically-similar but geographically-distant regions using thin laments “Niceness” of district shape almost always takes a back seat to political and racial concerns. Example: In the 2000 California realignment, Democrats and Republicans united to design incumbent-favoring districts, which resulted in the re-election of all of the 153 incumbents in 2004. How can one argue that this is in voters best interests?However, gerrymandering can be considered appropriate in specic situations. For instance, the Arizona Legislature gerrymandered a division between the historically hostile Hopi and Navajo tribes even though the Hopi reservation is entirely surrounded by the Navajo reservation.The Legality of Gerrymandering Though gerrymandering is objectionable to many, it is legal. The Voting Rights Act of 1965, which eliminated poll taxes and other discriminatory voting policies, may have inadvertently increased gerrymandering. One interpretation of the Act is that it mandates nondiscriminatory election results, which has led to a strange reversal of vocabulary in which creating “majority-minority” districts is considered benecial. These gerrymandered districts are packedwith minorities to guarantee minority representation in Congress. However, in Shaw v. Reno (1993), and later in Miller v. Johnson (1995), the Supreme Court ruled that racial/ethnic gerrymanders are unconstitutional. Nevertheless, Hunt v. Cromartie (1999) approved of a seemingly racial gerrymandering because the motivation was mostly partisan rather than racial. The recent case League of United Latin American Citizens v. Perry (June 2006) held that states are free to redistrict as often as they like so long as the redistrictings are not purely racially motivated.Assumptions and NotationWhat Can We Consider When Districting?1. The density of population in every districts.2. Contiguity of districts (legally mandated, excepting islands) 3. Respect for legal boundaries (counties, city limits, townships) 4. Respect for natural geographic boundaries 5. Compactness of district shapes 6. Population equality between districts (legally mandated) 7. Respect for human-made boundaries (highways, parks, etc.) 8. Respect for socioeconomic similarity of constituents 9. Similarity to past district boundaries 10. Partisan political concerns 11. Desire to make districts (un)competitive 12. Racial/ethnic concerns 13. Desire to protect (or unseat) incumbent politiciansThe Electoral district-dividing model 1. First of all, according to the population density in the state of 2 5 local population density of the larger point A1, A2.The An, then according to the structure of the voronoi diagram method, make the A1, A2.An outward expansion at the same speed, when the Ai and Aj namely stop when they met.By the nature of the voronoi diagram, Ai and Aj line must be a line segment, and get several large areas, such segmentation borderline in the middle of the get good satisfied we need simple principles.2. We need to each regional segmentation in Ai, then get the district division we need.Here we have each district population density, population statistics, P (Ai) for population, to determine the number of each district can be divided into districts.By sequencing to determine the number of regions can be divided into districts, divided into two cases to consider, is a district can be divided into the youth, the second is regional separable is large, we assume that how many boundaries for 14.3. For the partition of total population of Ai, with the first step on the same processing method, in these regions with the largest local population density point as the starting point and uniform distribution, determine the n points, outward radiation.4. Now make sure those partitions of n is greater than 14, we in New York City, for example.We have to calculate the number of regional population to determine the starting point, due to the variance of population distribution is huge, we need to find a function to fix it.For general voronoi diagram of the growth way this is obviously not applicable.Us for its growth speed to do some correction: V（x，y）=v0f（x，y） ,to f(x, y) point of population density, so that the greater the density place growth speed is more slow, its logical. B ASet within A population density of k, the population density in B is 2 kIf to 1, then by calculating the ratio of the total population of A and B is two to one, it is not reasonable. B A About voronoi Voronoi diagram, also called theissen polygon or Dirichlet figure, it is composed of a set of connection of two adjacent points straight line perpendicular bisector of continuous polygon.N points, with differences in the plane division in accordance with the principle of the adjacent plane;Each point is associated with its nearest neighbor area.Delaunay triangle by sharing an edge to the adjacent Voronoi polygon can be connected with the related points of the triangle.Delaunay triangle circumscribed circle circle is associated with the triangle Voronoi polygon a vertex.Voronoi triangle Delaunay graph is bipartite graph;brief introductionVoronoi diagram is a basic concept in computational geometry, lead to it by the following problems:Problem: N points in a given plane, for each point of Pi, the plane distance Pi points than the other points closer area is? Any point within the region (x, y), is apart from the Pi than other point in the plane are close.If the point set is composed of N points, Pi than at any other point distance closer point of area is the N - 1 contains Pi half plane intersection. This is N - 1 half plane by Pi points and other points of perpendicular bisector.V (I) is composed of some vertical split line polygon. With the above method to make the area of each point, to form the Voronoi diagram. It will be the whole plane is divided into N regions, each region contains a point, this area is the area of this point, the line segment or ray called Voronoi side, it must be two points of attachment midperpendicular period, known as the two points on the edge of the Voronoi points, related Voronoi edge between node called Voronoi vertices, the edge of the Voronoi related point is also the Voronoi vertex points. In addition, if the point (x, y) V (I), the Pi is the latest point to point (x, y).CharacteristicFor a given set of initial point P, there are a number of triangle mesh subdivision method, the Delaunay triangulation has the following features:1, the Delaunay triangulation is usually the only; (in the case of not only such as: P only contains four points, the four round)2, triangulation of outer boundary point set P of the convex polygon shell;3, there is no point in the inner circle of the triangle, on the other hand, if a triangle mesh to satisfy this condition, it is a Delaunay triangulation.4, if the triangulation of the smallest Angle of each triangle in ascending order, the arrangement of the Delaunay triangulation net value maximum, in this sense, the Delaunay triangulation is the most close to the regulation of the triangle mesh.The characteristics of the Delaunay triangular mesh and can be expressed as the following features:1. in the Delaunay triangle nets within the scope of any triangle circumcircle visibility with other points will not exist, namely empty round features;2.when is aralyzed, always choose the neighboring points form a triangle and line segments intersect with constraint;3. forming a triangle mesh is always the most optimal shape characteristics of arbitrary two adjacent triangles form a convex quadrilateral diagonal if can swap, then six inside the smallest Angle in the triangle will not become bigger;4. no matter starting from the area where is aralyzed, will eventually get consistent results, namely the structure network has uniqueness.basic standardAny a Delaunay triangle circumcircle cannot contain any other point within 1934 Delaunay. Lawson 1972 put forward the principle of maximizing the minimum Angle, every two adjacent triangle convex quadrilateral diagonal, after exchanging, six inside the minimum Angle is no longer increasing. Lawson 1977 proposed a local Optimization Procedure (LOP, local Optimization Procedure) method.general algorithmAny a Delaunay triangle circumcircle cannot contain any other point within 1934 Delaunay. Lawson 1972 put forward the principle of maximizing the minimum Angle, every two adjacent triangle convex quadrilateral diagonal, after exchanging, six inside the minimum Angle is no longer increasing. Lawson 1977 proposed a local Optimization Procedure (LOP, local Optimization Procedure) method.Any a Delaunay triangle circumcircle cannot contain any other point within 1934 Delaunay. Lawson 1972 put forward the principle of maximizing the minimum Angle, every two adjacent triangle convex quadrilateral diagonal, after exchanging, six inside the minimum Angle is no longer increasing. Lawson 1977 proposed a local Optimization Procedure (LOP, local Optimization Procedure) method.2, insert point of scattered points in turn, find its inscribed circle in the triangle list contains the insertion point of the triangle (known as the point of impact triangles), delete the influence the public side of the triangle, the insertion point with all affect the triangle vertices connected, so as to complete a point in the Delaunay triangle insert in the list.3, according to the rule of optimization of local newly formed triangle optimization (such as interchangeable diagonal). Put the triangle formed in Delaunay triangle list.4, loop through the above step 2 until all finished scatter insert.The triangulation algorithm based on scatter theory closely, uniqueness, grid meet empty round features, is more ideal. By its point insertion triangulation process shows that, after fulfilling the triangulation and create more new, dont need to make to construct network, all the points need to create the new triangle area with local networks, the influence of the method is simple and local networking. Also, delete, move also can rapid dynamically. But in practical application, the triangulation algorithm easily into the ground to line and characteristic line, when the larger point set is aralyzed speed is slower, if the scope of point set is convex area or the inner ring, will produce illegal triangle.In order to overcome the scatterplot triangulation algorithm based the above shortcomings, especially in order to improve the efficiency of algorithm, can empty circle characteristics of grid triangle a little relaxation, i.e. the triangulation method based on edge, the algorithm is briefly as follows:1, according to the existing line and characteristic line, form a list control.2, list a line as the bas