Generation of Tessellations using Continuous Optimization techniques

• Grant number: 16/20666-1
• Support Opportunities: Scholarships in Brazil - Master
• Start date: March 01, 2017
• End date: January 31, 2018
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Ernesto Julián Goldberg Birgin
• Grantee: Lucas Magno
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/05475-7 - Computational methods in optimization, AP.TEM

Abstract

This project consists in studying the generation of tessellations, namely, ways of dividing a domain in space into different regions. Among the possible choices we highlight Voronoi diagrams which, although simple, find applications in a multitude of areas. In particular, we will study the Centroidal Voronoi Tessellation and how its calculation can be modeled as a continuous optimization problem. Then, we intend to implement an algorithm based on quasi-Newton methods to solve this problem, introduced in Liu et al. [2009], in which the authors show its efficiency and robustness in comparison to the classical algorithm for calculating CVTs known as Lloyd's method. (AU)