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.