Graduation Year

2015

Date of Thesis Acceptance

Spring 5-13-2015

Major Department or Program

Mathematics

Advisor(s)

Albert Schueller

Abstract

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

36

Subject Headings

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

Permanent URL

http://hdl.handle.net/10349/20151083

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

Share

COinS
 

Rights Statement

Rights Statement

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/
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).