The sphere covering problem via convex algebraic geometry

• Grant number: 16/16999-5
• Support Opportunities: Scholarships in Brazil - Master
• Start date: October 01, 2016
• End date: February 28, 2018
• Field of knowledge: Physical Sciences and Mathematics - Mathematics - Applied Mathematics
• Principal Investigator: Gabriel Haeser
• Grantee: Leonardo Makoto Mito
• 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 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)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

BIRGIN, ERNESTO G.; GOMEZ, WALTER; HAESER, GABRIEL; MITO, LEONARDO M.; SANTOS, DAIANA O.. An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem. COMPUTATIONAL & APPLIED MATHEMATICS, v. 39, n. 1, MAR 2020. (16/16999-5, 13/05475-7, 17/17840-2, 18/24293-0, 17/18308-2)

BIRGIN, ERNESTO G.; GOMEZ, WALTER; HAESER, GABRIEL; MITO, LEONARDO M.; SANTOS, DAIANA O.. An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem. COMPUTATIONAL & APPLIED MATHEMATICS, v. 39, n. 1, p. 21-pg., 2020-03-01. (18/24293-0, 13/05475-7, 17/18308-2, 17/17840-2, 16/16999-5)

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 (IME/SBI) São Paulo.