Aplicaciones de estructuras de datos a problemas matemáticos: implementación del problema de seleccionar de un conjunto de puntos dado, los subconjuntos de cuatro puntos colineales.

Abstract

Among years, computational geometry has proposed various problems of interest, from which a large number of tools have been deployed. Those tools have helped to solve these particular problems, also, providing new tools to address more practical and efficient for both new and old problems. One of these questions is the problem of collinear points. The collinear points problem proposes that, given a set of points, find and report all possible subsets of collinear points. This document addresses two possible solutions to this problem and proposes a comparison of their performance. The first algorithm, labeled as brute force, analyses all possible combinations of points to determine collinearity. The algorithm does not use efficient tools to reach its solution. While second algorithm, addressed as intelligent, will take advantage of data structure tools such as binary trees and efficient data ordering algorithms in order to reach the same solution, but handling the initial set in a better way. The algorithms will be implemented in the programming language C++. They will be tested with randomly generated instances of different sizes. At the end, the efficiency of the algorithms will be compared.