This paper is concerned with the development of distributed spatial partitioning algorithms for locational optimization problems involving networks of agents with planar rigid body dynamics subject to communication constraints. The domain of the problems we consider is a three-dimensional (3-D) nonflat manifold embedded in the state space of the agents, which we refer to as the terminal manifold. The approach we propose allows us to associate the partition of the 3-D terminal manifold, which is induced by a nonquadratic proximity metric and comprised of nonconvex cells, with a one-parameter family of partitions of 2-D flat manifolds, which are induced by (parametric) quadratic proximity metrics and comprised of convex polygonal cells. By exploiting the special structure of the parametric partitions, we develop distributed partitioning algorithms that converge in a finite number of steps. Subsequently, we utilize the solutions to the latter problems to solve a class of locational optimization problems over the terminal manifold. Numerical simulations that illustrate the capabilities of the proposed algorithms are also presented.