Conjuntos convexos e algoritmos para construir invólucros convexos

Abstract

Esta dissertação tem como principal objectivo a apresentação de um conjunto de algoritmos que determinam invólucros convexos no espaço bidimensional e no espaço tridimensional. Para tal, começa-se por efectuar um estudo breve sobre conjuntos convexos, apresentando os resultados mais significativos deste tipo de conjuntos. Em seguida, são apresentados algoritmos que determinam invólucros convexos no plano, efectuando-lhes um estudo em termos de complexidade e comparando-os, sempre que oportuno, com outros algoritmos. Finalmente, é feita a extensão de dois destes algoritmos ao espaço tridimensional.

The main goal of this dissertation is to present a set of algorithms that determine convex hulls in the bidimensional space and tridimensional space. To do that, is done a brief study about convex sets, presenting the most significant results about this type of sets. Next, are presented algorithms to determine convex hulls on the plane, studying their complexity and compare them with other algorithms. Finally, is made an extension of two algorithms in the tridimensional space.