@TechReport{ChagasQueiArak:2016:AnCoAl,
               author = "Chagas, Jo{\~a}o Vitor and Queiroz, Gilberto Ribeiro de and 
                         Arakaki, Reinaldo Gen Ichiro",
                title = "An{\'a}lise comparativa de algoritmos para computa{\c{c}}{\~a}o 
                         de pontos de intersec{\c{c}}{\~a}o entre conjuntos de segmentos 
                         de reta em m{\'a}quinas multi-core",
          institution = "Instituto Nacional de Pesquisas Espaciais",
                 year = "2016",
                 type = "RPQ",
              address = "S{\~a}o Jos{\'e} dos Campos",
                 note = "{Bolsa PIBIC/INPE/CNPq}",
             keywords = "SIG. Algoritmo Intersec{\c{c}}{\~a}o.",
             abstract = "A computa{\c{c}}{\~a}o dos pontos de intersec{\c{c}}{\~a}o 
                         entre conjuntos de segmentos de reta {\'e} considerado um dos 
                         problemas mais relevantes para um Sistema de 
                         Informa{\c{c}}{\~a}o Geogr{\'a}fica (SIG), sendo a base para a 
                         constru{\c{c}}{\~a}o de diversas opera{\c{c}}{\~o}es 
                         encontradas neste tipo de sistema. A computa{\c{c}}{\~a}o de 
                         tais pontos envolve um grande consumo de processamento, 
                         principalmente, para grandes entradas de dados. Tanto na 
                         literatura de Geometria Computacional quanto na de 
                         Geoinform{\'a}tica, encontramos diversos algoritmos para 
                         solu{\c{c}}{\~a}o deste problema. No entanto, esses algoritmos 
                         possuem diferentes compromissos de desempenho versus complexidade 
                         de implementa{\c{c}}{\~a}o, propiciando um substancial desafio 
                         para desenvolvedores e projetistas de SIGs, no que diz respeito 
                         {\`a} escolha, refinamento e implementa{\c{c}}{\~a}o desses 
                         algoritmos. Al{\'e}m disso, grande parte dos algoritmos foram 
                         desenvolvidos em uma {\'e}poca em que n{\~a}o existia as atuais 
                         arquiteturas de processadores multi-core e, consequentemente, 
                         foram projetados de forma sequencial ou de dif{\'{\i}}cil 
                         paraleliza{\c{c}}{\~a}o. Neste trabalho, examinamos um conjunto 
                         de algoritmos de intersec{\c{c}}{\~a}o entre conjuntos de 
                         segmentos de reta for{\c{c}}a-bruta, x-ordering, fixed-grid e 
                         tiling-scheme, e como adapt{\'a}-los para ambientes paralelos, 
                         utilizando o modelo de programa{\c{c}}{\~a}o multithread. Nossas 
                         an{\'a}lises foram realizadas com base em testes 
                         emp{\'{\i}}ricos realizados com a implementa{\c{c}}{\~a}o em 
                         C++ de vers{\~o}es sequenciais dos algoritmos e posterior 
                         paraleliza{\c{c}}{\~a}o, utilizando dados geogr{\'a}ficos reais 
                         acessados atrav{\'e}s da biblioteca TerraLib. Os resultados 
                         obtidos mostram que os algoritmos sequenciais s{\~a}o bem 
                         competitivos quando comparados com a solu{\c{c}}{\~a}o trivial 
                         do problema. Al{\'e}m disso, mostram um ganho significativo em se 
                         paralelizar partes das instru{\c{c}}{\~o}es desses algoritmos.",
          affiliation = "{Faculdade Tecnol{\'o}gica (FATEC)} and {Instituto Nacional de 
                         Pesquisas Espaciais (INPE)} and {Faculdade Tecnol{\'o}gica 
                         (FATEC)}",
             language = "pt",
                pages = "67",
                  ibi = "8JMKD3MGP3W34R/42PMN55",
                  url = "http://urlib.net/ibi/8JMKD3MGP3W34R/42PMN55",
           targetfile = "Chagas_analise.pdf",
        urlaccessdate = "13 maio 2024"
}