Optimal Arrangements of Rigid Shapes--A Voronoi Approach.
Lisa Larsson, CIMS

Given a finite collection of shapes, we optimize their location via translation and rotation by minimizing a suitable cost function.  This cost function dictates that the shapes should be well-centered within their generalized Voronoi regions, and is an extension of the well-known centroidal Voronoi tessellation (CVT) for points.  The CVT optimization problem for points is typically tackled using quasi-Newton methods and an iterative algorithm called Lloyd's method--we will discuss extensions of both to the case of shapes.  The optimization problem for shapes is challenging in part because integrals over generalized Voronoi regions must be calculated. One novelty of our algorithm is that the generalized Voronoi diagram is never explicitly calculated. The optimization problem and integration algorithm will be presented, along with numerical results.