The sphere covering problem via convex algebraic geometry

• Grant number: 16/16999-5
• Support type: Scholarships in Brazil - Master
• Effective date (Start): October 01, 2016
• Effective date (End): February 28, 2018
• Field of knowledge: Physical Sciences and Mathematics - Mathematics
• Principal Investigator: Gabriel Haeser
• Grantee: Leonardo Makoto Mito
• Home 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 research project is focused on a classic problem from engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to find a different way. Here, we propose to explore some renowned results from convex algebraic geometry, which has Stengles positivstellensatz as its central piece, and SOS optimization, once the proper link is made, the original problem can be reduced to a semidefinite programming one, which has an algorithmic solution. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects. (AU)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MITO, Leonardo Makoto. The covering problem via convex algebraic geometry. 2018. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Matemática e Estatística São Paulo.