Um algoritmo geométrico para o problema de inclusão no envoltório convexo

Abstract

O problema de inclusão no envoltório convexo consiste em determinar se um certo ponto pertence ao envoltório convexo de um conjunto de n pontos. Este problema encontra importantes aplicações em geometria computacional e programação linear. Apresentamos um estudo teórico e prático de um Algoritmo Geométrico proposto em (B. Kalantari, Ann Oper Res (2015) 226:301?349), que tem como base um teorema de separação chamado de Dualidade de Distâncias. Na análise teórica do algoritmo, fornecemos algumas demonstrações alternativas ao artigo original, sob um ponto de vista próprio, fundamentado em conceitos de otimização contínua. Este ponto de vista nos permitiu propor duas variações para o Algoritmo Geométrico, além de estabelecer a relação deste com o clássico algoritmo de Frank-Wolfe. Também estudamos o comportamento prático do algoritmo em instâncias artificiais do problema, comparando-o com algoritmos clássicos de otimização para reformulações lineares e quadráticas. Os resultados obtidos sugerem o Algoritmo Geométrico como uma alternativa promissora para o problema de inclusão no envoltório convexo.

Abstract: The convex hull membership problem consists in deciding whether a certain point belongs to the convex hull of a set of n points. This problem finds interesting applications on computational geometry and linear programming. We present a theoretical and practical study of a geometric algorithm proposed in (B. Kalantari, Ann Oper Res (2015) 226:301?349), which is based on a separation theorem known as Distance Duality. In the theoretical analysis, we provide alternative proofs for some results, under our own perspective, relying on concepts of continuous optimization. This new point of view allowed us to develop two variants of the geometric algorithm and also establish its relation with the classical Frank-Wolfe method. We also assessed the pratical behaviour of the algorithm in artificially generated instances and compare its performance with classical optimization algorihtms for linear and quadratic programming reformulations of the problem. The numerical results suggest the geometric algorithm as a promissing alternative for the convex hull membership problem.