Please use this identifier to cite or link to this item: http://bibdigital.epn.edu.ec/handle/15000/23169
Title: Implementación del problema de encontrar todas las intersecciones de N rectas horizontales y verticales: mplementación de estructuras en C++.
Authors: Pionce Gallardo, Luis Enrique
Keywords: ALGORITMO
TEORÍA COMPUTACIONAL
ESTRUCTURA DE DATOS
LENGUAJE DE PROGRAMACIÓN
ÁRBOL BINARIO
Issue Date: Oct-2022
Publisher: Quito : EPN, 2022.
Citation: Pionce Gallardo, L.E.(2022). Implementación del problema de encontrar todas las intersecciones de N rectas horizontales y verticales: Implementación de estructuras en C++. 46 páginas. Quito : EPN.
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.
Description: En el presente trabajo de integración curricular se implementó un algoritmo propuesto por Jon L. Bentley y Thomas A. Ottmann (1979), para encontrar y reportar todas las intersecciones de un conjunto de segmentos de recta verticales y horizontales. Se comenzó definiendo ciertos elementos de la teoría computacional, además se definieron las estructuras de datos que fueron utilizadas en el algoritmo. El algoritmo fue implementado en el lenguaje de programación C++. En el desarrollo del algoritmo se realizaron dos variantes del mismo algoritmo, cuya variante consiste en la estructura de datos para almacenar los segmentos, primero se utilizó un árbol binario de búsqueda y luego un árbol binario de búsqueda auto-balanceado, este último permite mejorar los tiempos de ejecución del algoritmo. Para poner en ejecución los algoritmos desarrollados, se construyeron las instancias simulando segmentos de recta aleatorios. También se implementó un algoritmo de fuerza bruta. Finalmente, se ejecutaron distintas instancias, poniendo a prueba los algoritmos y comparándolos en términos de eficiencia.
URI: http://bibdigital.epn.edu.ec/handle/15000/23169
Appears in Collections:TIC- Ingeniería Matemática

Files in This Item:
File Description SizeFormat 
CD 12593.pdf1,32 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.