  The topic of this paper is "gerrymandering", namely the curse of deliberate
creations of district maps with highly asymmetric electoral outcomes to
disenfranchise voters, and it has a long legal history. Measuring and
eliminating gerrymandering has enormous implications to sustain the backbone of
democratic principles of a society. Although there is no dearth of legal briefs
involving gerrymandering over many years, it is only more recently that
mathematicians and applied computational researchers have started to
investigate this topic. However, it has received relatively little attention so
far from the computational complexity researchers dealing with theoretical
analysis of computational complexity issues, such as computational hardness,
approximability issues, etc. There could be many reasons for this, such as
descriptions of these problem non-CS non-math (often legal or political)
journals that theoretical CS (TCS) people usually do not follow, or the lack of
coverage of these topics in TCS publication venues. One of our modest goals in
writing this article is to improve upon this situation by stimulating further
interactions between the gerrymandering and TCS researchers. To this effect,
our main contributions are twofold: (1) we provide formalization of several
models, related concepts, and corresponding problem statements using TCS
frameworks from the descriptions of these problems as available in existing
non-TCS (perhaps legal) venues, and (2) we also provide computational
complexity analysis of some versions of these problems, leaving other versions
for future research.
  The goal of writing this article is not to have the final word on
gerrymandering, but to introduce a series of concepts, models and problems to
the TCS community and to show that science of gerrymandering involves an
intriguing set of partitioning problems involving geometric and combinatorial
optimization.
