Graduation Year


Date of Thesis Acceptance

Spring 5-13-2015

Major Department or Program



Albert Schueller


A centroidal Voronoi tessellation (CVT) is a special kind of Voronoi tessellation such that the generating points of the tessellation are also the mass centroids of the corresponding regions. Due to their innate optimization properties, CVTs have applications in diverse fields; however, the theoretical nature of these tessellations is far from well understood. We approach some open questions about CVTs by looking in particular at 2-point tessellations of regular polygons with constant density. We show that for any CVT of an even-sided polygon, the Voronoi boundary or the centroids must lie on lines of symmetry, and anticipate that the same is true for odd-sided polygons. We predict which of these configurations are stable under Lloyd's algorithm for computing CVTs. Finally, we illustrate basins of attraction for the stable CVTs under Lloyd's algorithm.

Page Count


Subject Headings

Algorithm -- Lloyd’s algorithm, Voronoi-diagramm, Mathematics -- Theory & applications, Voronoi polygons -- boundaries, Tessellations (Mathematics) -- centroidal voronoi tessellations, Voronoi polygons -- density, Tessellations (Mathematics) -- points, Algorithms -- Data processing, Discrete geometry, Whitman College -- Dissertation collection 2015 -- Mathematics Department

Permanent URL

Document Type

Public Accessible Thesis

Terms of Use

If you have questions about permitted uses of this content, please contact the ARMINDA administrator

Included in

Mathematics Commons



Rights Statement

Rights Statement

In Copyright. URI:
This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).