  Manipulation, bribery, and control are well-studied ways of changing the
outcome of an election. Many voting rules are, in the general case,
computationally resistant to some of these manipulative actions. However when
restricted to single-peaked electorates, these rules suddenly become easy to
manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the
computational complexity of strategic behavior in nearly single-peaked
electorates. These are electorates that are not single-peaked but close to it
according to some distance measure.
  In this paper we introduce several new distance measures regarding
single-peakedness. We prove that determining whether a given profile is nearly
single-peaked is NP-complete in many cases. For one case we present a
polynomial-time algorithm. In case the single-peaked axis is given, we show
that determining the distance is always possible in polynomial time.
Furthermore, we explore the relations between the new notions introduced in
this paper and existing notions from the literature.
