  Gerrymandering is a long-standing issue within the U.S. political system, and
it has received scrutiny recently by the U.S. Supreme Court. In this note, we
prove that deciding whether there exists a fair redistricting among legal maps
is NP-hard. To make this precise, we use simplified notions of "legal" and
"fair" that account for desirable traits such as geographic compactness of
districts and sufficient representation of voters. The proof of our result is
inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that
planar k-means is NP-hard.

Computational Complexity;Data Structures and Algorithms