Implementación del problema de encontrar todas las intersecciones de N rectas horizontales y verticales: mplementación de estructuras en C++.

Abstract

In this work, an algorithm proposed by Jon L. Bentley and Thomas A. Ottmann (1979) was implemented with the aim of finding and reporting all the intersections of a set of vertical and horizontal line segments. It began by defining elements of the computational theory; then, the data structures used in the algorithm were defined.

The algorithm was implemented in C++ programming language. In the development of the algorithm, two variants of the same algorithm were carried out. Each variant corresponds to a data structure used to store the segments, first a binary search tree was used and then a self-balancing binary search tree. The latter improve algorithm performance. To implement the developed algorithms, the instances were built simulating random line segments. A brute force algorithm was also implemented. Finally, different instances were executed, testing the algorithms and comparing them in terms of efficiency.