Informações:

Publicações do PESC

Título
Sobra o Problema Euclidiano de Steiner em RN
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
7/4/2017
Resumo

O Problema Euclidiano de Steiner (PES) tem como objetivo determinar uma rede de comprimento mínimo que conecte um conjunto finito de pontos do Rn previamente escolhidos. A norma utilizada é a euclidiana e é permitido o uso de pontos extras que possam contribuir para a redução do comprimento final da rede. Problemas desta natureza são frequentemente encontrados em diversas áreas da matemática, engenharia, etc.

Neste trabalho, estudamos as origens do PES, suas propriedades, complexidade e métodos de resolução. Encerramos analisando uma conjectura proposta em 1992 por Warren Smith sobre a aplicação desse problema aos vértices de um hipercubo n-dimensional, a qual está em aberto desde sua publicação.

Abstract

The Euclidean Steiner Problem (ESP) asks for a network of minimum length interconnecting a finite set of given points in Rn. The distances considered are Euclidean and it's allowed to add additional points to decrease the overall length of the network. Problems of this nature are often found in several areas of mathematics, engineering, etc.

In this work, we study the origins of ESP, their properties, complexity, and resolution methods. We conclude by analyzing a conjecture proposed in 1992 by Warren Smith on the application of this problem to the vertices of an n-dimensional hypercube, which has remained open since its publication.

Arquivo
Topo