  Mesh partitioning is an indispensable tool for efficient parallel numerical
simulations. Its goal is to minimize communication between the processes of a
simulation while achieving load balance. Established graph-based partitioning
tools yield a high solution quality; however, their scalability is limited.
Geometric approaches usually scale better, but their solution quality may be
unsatisfactory for `non-trivial' mesh topologies.
  In this paper, we present a scalable version of $k$-means that is adapted to
yield balanced clusters. Balanced $k$-means constitutes the core of our new
partitioning algorithm Geographer. Bootstrapping of initial centers is
performed with space-filling curves, leading to fast convergence of the
subsequent balanced k-means algorithm.
  Our experiments with up to 16384 MPI processes on numerous benchmark meshes
show the following: (i) Geographer produces partitions with a lower
communication volume than state-of-the-art geometric partitioners from the
Zoltan package; (ii) Geographer scales well on large inputs; (iii) a Delaunay
mesh with a few billion vertices and edges can be partitioned in a few seconds.
