Search

El objetivo general del trabajo es construir nuevas funciones de profundidad, entendidas como el grado de centralidad de un punto respecto a una distribución multivariante, y sus respectivas regiones centrales. La utilidad de estas construcciones en el campo multivariante radica en que permiten construir un orden según el grado de centralidad que puede utilizarse para extender ciertas técnicas de estadística univariate que se basan en la relación de orden menor o igual. El trabajo está enmarcado en la Estadística Matemática, utiliza nociones y técnicas de Análisis Convexo, mientras que los algoritmos para calcular profundidades y regiones pueden ubicarse dentro de la Geometría Computacional. La tesis está dividida en cuatro partes claramente diferenciadas. En primer lugar un capítulo que contiene un marco teórico general, en el que se presentan de forma muy intuitiva las ideas de expectiles y funciones de profundidad, así como sus propiedades y algunas de las aplicaciones más conocidas. En segundo lugar un capítulo dedicado a la construcción de la profundidad expectílica, en el que, por la misma naturaleza de los expectiles, se logran formalizar algunos resultados de tipo asintótico, además de explotar la idea de regiones expectílicas en el ámbito del análisis descriptivo bivariado. Dado que, tal como se ilustra con datos simulados, las regiones expectílicas son sensibles a la presencia de datos extremos, nace el tercer capítulo, en el que se usa una familia de M-cuantiles distorsionados que generalizan inmediatamente a los expectiles. Las regiones asociadas a los M-cuantiles distorsionados son estudiadas desde el punto de vista analítico y geométrico, mostrando resaltando partcularmente la robustez frente a la presencia de outliers. Finalmente un capítulo donde se presenta la noción de regresión M-cuantílica de respuesta múltiple, a partir de la cual se logra construir una nueva familia de regiones centrales, llamadas regiones de regresión, que resultan ser una herramienta descriptiva de la distribución conjunta de las variables explicadas para un nivel dado del vector de regresores. Se muestra, además, cómo a partir de estas últimas regiones se puede obtener una nueva noción de profundidad, se analizan algunas de sus propiedades así como posibles aplicaciones en diferentes campos de estudio. Por último, se cierra el trabajo con la sección de conclusiones y algunas sugerencias para futuras investigaciones. Programa de Doctorado en Ingeniería Matemática por la Universidad Carlos III de Madrid Presidente: Antonio Cuevas González.- Secretaria: Ana Arribas Gil.- Vocal: Alfonso Suárez Lloréns

Treballs finals del Màster en Matemàtica Avançada, Facultat de Matemàtiques, Universitat de Barcelona: Curs: 2021-2022. Director: Carles Casacuberta i Aina Ferrà Marcús, [en] Topological Data analysis has been extensively used to solve point cloud classification problems; however, how to use TDA in classification of points in $\mathbb{R}^2$ has not been studied yet. In this work we use recently developed tools on the study of random persistence diagrams in order to deal with the classification of points in $\mathbb{R}^d$.

Submitted by Leda Lopes (ledacplopes@hotmail.com) on 2022-09-23T14:23:39Z No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Débora_Marília_Hauenstein_Dissertação.pdf: 2024845 bytes, checksum: ca6e10191012bdc7bd1d7f896ca6a1b3 (MD5) Débora_Marília_Hauenstein_Produto.pdf: 997528 bytes, checksum: f67c9024874aa6517c3a2a7c4bba22b4 (MD5) Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2022-09-23T20:46:54Z (GMT) No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Débora_Marília_Hauenstein_Dissertação.pdf: 2024845 bytes, checksum: ca6e10191012bdc7bd1d7f896ca6a1b3 (MD5) Débora_Marília_Hauenstein_Produto.pdf: 997528 bytes, checksum: f67c9024874aa6517c3a2a7c4bba22b4 (MD5) Made available in DSpace on 2022-09-23T20:47:07Z (GMT). No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Débora_Marília_Hauenstein_Dissertação.pdf: 2024845 bytes, checksum: ca6e10191012bdc7bd1d7f896ca6a1b3 (MD5) Débora_Marília_Hauenstein_Produto.pdf: 997528 bytes, checksum: f67c9024874aa6517c3a2a7c4bba22b4 (MD5) Previous issue date: 2022-08-23 A presente pesquisa objetiva desenvolver, aplicar e analisar uma prática didática utilizando recursos da tecnologia da informação e comunicação, com auxílio do software GeoGebra e de tópicos da geometria computacional, para identificar elementos que possam contribuir para a melhoria dos índices de desempenho, e entendimento das dificuldades de aprendizagem, dos discentes matriculados na disciplina Geometria Analítica do Ensino Superior. O referencial teórico foi baseado na identificação de dificuldades de aprendizagem de estudantes em relação a conteúdos e em como as tecnologias educacionais poderiam contribuir para seu ensino, dando ênfase para recursos da geometria computacional e para experiências que usam o GeoGebra. A investigação é de cunho qualitativo, ancorada na pesquisa documental por meio de revisões bibliográficas que fundamentam as problemáticas de aprendizagem e as estratégias de ensino utilizadas na produção de uma sequência didática. Também realiza-se um estudo que envolve a aplicação desse produto com sujeitos de pesquisa do curso de graduação de Licenciatura em Matemática que estão cursando a disciplina Geometria Analítica em um Instituto Federal situado no Rio Grande do Sul. Na execução da pesquisa foram utilizados como instrumentos para coleta de dados listas de exercícios com questões discursivas e objetivas, além de construções elaboradas com o GeoGebra ao longo das aulas. Os resultados apontam um aumento na entrega de atividades dos estudantes e o despertar do interesse frente ao uso dos recursos computacionais em sala de aula. A prática apresenta indícios de que pode qualificar o processo de ensino dos conteúdos, tornando-o dinâmico e participativo para o estudante, proporcionando liberdade e pensamento crítico ao solucionar questões matemáticas da Geometria Analítica. Ao fim, indicamos alguns possíveis trabalhos futuros que podem dar continuidade ao estudo. The present research aims to develop, apply and analyze a didactic practice using information and communication technology resources, with the help of GeoGebra software and computational geometry topics, to identify elements that can contribute to the improvement of performance indices, and understanding of the learning difficulties, of students enrolled in the discipline Analytical Geometry of Higher Education. The theoretical framework was based on the identification of students' learning difficulties in relation to content and on how educational technologies could contribute to their teaching, emphasizing computational geometry resources and experiences using GeoGebra. The investigation is of a qualitative nature, anchored in documental research through bibliographic reviews that support the learning issues and teaching strategies used in the production of a didactic sequence. A study is also carried out that involves the application of this product with research subjects from the Mathematics Degree course who are studying Analytical Geometry at a Federal Institute located in Rio Grande do Sul. In carrying out the research, lists of exercises with discursive and objective questions were used as instruments for data collection, as well as constructions developed with GeoGebra throughout the classes. The results point to an increase in the delivery of student activities and the awakening of interest in the use of computing resources in the classroom. The practice shows evidence that it can qualify the content teaching process, making it dynamic and participatory for the student, providing freedom and critical thinking when solving mathematical issues of Analytical Geometry. At the end, we indicate some possible future works that can continue the study.

En aquest projecte hem considerat dos problemes oberts de separació de punts vermells i blaus en el pla, contextualitzats en el camp de la geometria computacional. Partint de resultats ja coneguts, hem estès i millorat els algoritmes, concretament per la separabilitat emprant 4 rectes paral·leles en tires monocromàtiques. I hem analitzat condicions suficients per a aquests criteris de separabilitat. In this project, we have tackled two open questions regarding the separability of red and blue points in the plane, from the framework of computational geometry. Building on existing results, we have extended and improved algorithms, specifically for the separability using 4 parallel lines that define monochromatic strips. Also, sufficient conditions to meet these separability criteria have been studied.

El doblez proyectado es indisoluble de la geometría que lo hace posible. Para establecer un claro control sobre el doblez es necesario realizar un documento proyectivo, un plano. Es por eso que los asuntos ligados a la geometría y al control matemático de los patrones de doblado han sido siempre fundamentales en la construcción de este tipo de diseños. Nos acercamos aquí a uno de los principales referentes y precursores sobre el estudio y desarrollo de los patrones de doblado para fines volumétricos, Ron Resch. Se trata de un desconocido artista y científico computacional norteamericano cuyo trabajo se menciona de modo repetido cuando se habla de arquitectos contemporáneos como Greg Lynn, quien ha aplicado también el uso del ordenador como herramienta de control y desarrollo geométrico. Para situar el momento, veremos el trabajo didáctico de Josef Albers y su manera de “abrir los ojos” mediante la experiencia con la manipulación restringida de la materia. El trabajo de Ron Resch establece una manera científica de aproximarse al problema y de aplicar las por aquel entonces incipientes herramientas computacionales, como son la elaboración de modelos 3D o la utilización de maquinaria CNC para el corte o el marcado. Los sistemas topológicos de Resch son en gran medida el origen de lo que hoy es el diseño paramétrico y la arquitectura de desarrollo con ordenadores.

This study provides a system that determines where to locate 𝑘 disks-like services of radius 𝑟 so that they globally cover as much as possible a region of demand. It is an NP-hard problem with notorious applications in the facility location field when locating multiple warning sirens, cellular towers, radio stations, or pollution sensors covering as much area as possible of a city or geographical region. The region of demand is assumed to be delimited by a general polygonal domain, and the resolution strategy relies on a parallel simulated annealing optimization technique based on a suitable perturbation strategy and a probabilistic estimation of the area of the polygonal region covered by the 𝑘 disks in 𝑂(𝑘2) time. The system provides a good enough location for the disks starting from an arbitrary initial solution with very reasonable running times. The proposal is experimentally tested by visualizing the solutions, analyzing and contrasting their quality, and studying the computational efficiency of the entire strategy Open Access funding provided thanks to the CRUE-CSIC agreement with Elsevier

This Doctoral Thesis develops novel articulations of Computation Geometry for applications on Additive Manufacturing, as follows: (1) Shape Optimization in Lattice Structures. Implementation and sensitivity analysis of the SIMP (Solid Isotropic Material with Penalization) topology optimization strategy. Implementation of a method to transform density maps, resulting from topology optimization, into surface lattice structures. Procedure to integrate material homogenization and Design of Experiments (DOE) to estimate the stress/strain response of large surface lattice domains. (2) Simulation of Laser Metal Deposition. Finite Element Method implementation of a 2D nonlinear thermal model of the Laser Metal Deposition (LMD) process considering temperaturedependent material properties, phase change and radiation. Finite Element Method implementation of a 2D linear transient thermal model for a metal substrate that is heated by the action of a laser. (3) Process Planning for Laser Metal Deposition. Implementation of a 2.5D path planning method for Laser Metal Deposition. Conceptualization of a workflow for the synthesis of the Reeb Graph for a solid region in ℝ" denoted by its Boundary Representation (B-Rep). Implementation of a voxel-based geometric simulator for LMD process. Conceptualization, implementation, and validation of a tool for the minimization of the material over-deposition at corners in LMD. Implementation of a 3D (non-planar) slicing and path planning method for the LMD-manufacturing of overhanging features in revolute workpieces. The aforementioned contributions have been screened by the international scientific community via Journal and Conference submissions and publications.

Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2-(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 48:1-48:17

Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2022, Director: Carles Casacuberta i Aina Ferrà Marcús, [en] Mapper is one of the principal tools in topological data analysis (TDA) that enables studying topological features of high-dimensional datasets. Many studies from different fields, such as medicine and sports, have recently applied the Mapper algorithm to extract outstanding information from data. In this work, our goal is to substantiate the conclusions from Comparison between endocardial and epicardial cardiac resynchronization in an experimental model of nonischaemic cardiomyopathy study. In particular, we look for the optimal heart region where cardiac resynchronisation therapy offers a better result. Even though the core of the study is practical, we also profoundly study the theory behind the Mapper algorithm and the statistical methods we apply throughout the process.

Esta tesis trata sobre varios problemas en el área de la geometría discreta y computacional, relacionados con grafos, polígonos y conjuntos de puntos en el plano. La tesis ha sido realizada mediante el compendio de cuatro artículos publicados en revistas. Tras un capítulo introductorio, el capítulo 2 trata sobre el problema del cálculo del núcleo de un polígono llevado al ámbito de la geometría con orientaciones restringidas. En particular, obtenemos un algoritmo para calcular y mantener el O-núcleo de un polígono conforme el conjunto de orientaciones O rota. Este algoritmo proporciona, además, los ángulos de rotación para los que el área y el perímetro del O-núcleo son máximos. En el capítulo 3, estudiamos una versión bicromática de un problema clásico de geometría combinatoria: Dado un conjunto de puntos en ¿¿ el plano, existen dos puntos tal que todos los círculos que los tienen en su frontera contienen en su interior al menos ¿¿(1 ¿ 1/¿2) ¿ ¿¿(¿¿) otros puntos del conjunto. Este problema combinatorio está fuertemente ligado a los diagramas de Voronoi de orden superior del conjunto de puntos. En los capítulos 4 y 5, planteamos dos aplicaciones de la teoría de grafos al análisis sensorial y al control del tráfico aéreo, respectivamente. En el primer caso, proponemos un método que utiliza técnicas geométricas para analizar las opiniones de los consumidores recogidas con mapeo proyectivo. En el segundo, utilizamos la técnica del espectro-coloreado de grafos para plantear un modelo del tráfico aéreo que pretende optimizar el consumo de combustible de los aviones al mismo tiempo que se evitan colisiones entre ellos., This thesis deals with problems and applications of discrete and computational geometry in the plane, concerning polygons, point sets, and graphs. After a first introductory chapter, in Chapter 2 we study a generalization of a famous visibility problem in the framework of O-convexity. Given a set of orientations (angles) O, we say that a curve is O-convex if its intersection with any line parallel to an orientation in O is connected. When O = {0◦, 90◦}, we find ourselves in the case of orthoconvexity, considered of special relevance. The O-kernel of a polygon is the subset of points of the polygon that can be connected to any other point of the polygon with an O-convex curve. In this work we obtain, for O = {0◦} and O = {0◦, 90◦}, an algorithm to compute and maintain the O-kernel of a polygon as the set of orientations O rotates. This algorithm also provides the angles of rotation that maximize the area and perimeter of the O-kernel. In Chapter 3, we consider a bichromatic version of a combinatorial problem posed by Neumann-Lara and Urrutia. Specifically, we prove that every set of n blue and n red points in the plane contains a bichromatic pair of points such that every circle having them on its boundary contains at least n(1 − √12) − o(n) points of the set in its interior. This problem is closely related to obtaining the higher order Voronoi diagrams of the point set. The edges of these diagrams contain, precisely, all the centers of the circles that pass through two points of the set. Therefore, our current line of research on this problem consists on exploring this connection by studying in detail the properties of higher order Voronoi diagrams. In Chapters 4 and 5, we consider two applications of graph theory to sensory analysis and air traffic management, respectively. In the first case, we introduce a new method which combines geometric and statistical techniques to analyze consumer opinions, collected through projective mapping. This method is a variation of the method SensoGraph. It aims to capture the essence of projective mapping by computing the Ecuclidean distances between pairs of samples and normalizing them to the interval [0, 1]. We apply the method to a real-life scenario and compare its performance with the performance of classic methods of sensory analysis over the same data set. In the second case, we use the Spectrum Graph Coloring technique to propose a model for air traffic management that aims to optimize the amount of fuel used by the airplanes, while avoiding collisions between them.

Orientadores: Pedro Jussieu de Rezende, Cid Carvalho de Souza Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Problemas de decomposição, que incluem particionamento, cobertura e empacotamento, constituem um assunto central em Pesquisa Operacional. Estudamos variações geométricas NP-difíceis desses problemas no plano e apresentamos modelos de programação linear inteira (PLI) e heurísticas para eles. Lançamos também as bases para mais investigações com novos algoritmos e estruturas de dados, juntamente com benchmarks disponibilizados publicamente. Em primeiro lugar, estudamos o Problema da Partição Convexa Mínima de Conjuntos de Pontos, cujo objetivo é particionar a envoltória convexa de um conjunto de pontos P em um número mínimo de polígonos convexos vazios (sem pontos de P em seu interior) com vértices em P. Propomos um modelo PLI baseado em grafos e outro baseado em arranjos. Para o segundo modelo, fornecemos uma implementação eficiente utilizando geração de colunas, juntamente com heurísticas, pré-processamento e regras de ramificação geométricas. Identificamos um pequeno subconjunto de faces do arranjo, ou seja, restrições, suficientes para expressar o modelo, bem como uma estrutura de dados que permite consultas rápidas sobre somas de variáveis duais associadas a elas. Em segundo lugar, investigamos a Quadrangulação Convexa de Conjuntos de Pontos Bicromáticos com Inversões Mínimas. Nesse problema, dado um conjunto de pontos bicromático P, pede-se para encontrar o número mínimo de inversões de cores que permite que a envoltória convexa de P seja particionada em quadriláteros convexos vazios com vértices em P e cujas arestas têm extremidades de cores diferentes. Introduzimos um modelo PLI baseado em grafos e outro baseado em arranjos. O segundo modelo é uma nova abordagem que nos permite expressar coloração e particionamento do espaço como um modelo compacto de particionamento. Usamos esse modelo para derivar heurísticas análogas a abordagens de emparelhamento da literatura. Em terceiro lugar, estudamos o problema da Coesão em que, dado um conjunto de pontos bicromático P, busca-se particioná-lo usando polígonos convexos maximizando a diferença mínima no número de pontos de cada cor cobertos por cada polígono. Descrevemos um modelo PLI com número exponencial de variáveis que é eficientemente implementado usando geração de colunas. A combinação da relaxação desse modelo com uma heurística da literatura produz um algoritmo iterativo de pré-processamento polinomial. Esse algoritmo foi capaz de resolver otimamente grande parte do nosso benchmark. Finalmente, estudamos um problema de cobertura inspirado em redes sem fio, chamado de Cobertura Mínima 3-Colorível por Discos Unitários. Neste problema, dado um conjunto de pontos P e um conjunto D de discos de mesmo raio, deseja-se encontrar uma cobertura mínima de P selecionando um subconjunto de D que pode ser colorido com até 3 cores. Descrevemos um modelo PLI e mostramos como ele pode ser estendido e implementado iterativamente usando Decomposição de Benders Baseada em Lógica. Essa decomposição tem um problema mestre de cobertura e um subproblema de 3-coloração. Provamos que a solução da primeira iteração usa no máximo 18 vezes o menor número de cores dentre todas as coberturas de P por D. Também apresentamos algoritmos geométricos e baseados em resultados de teoria de grafos para obter cortes mais fortes, reduzindo significativamente o tempo de execução Abstract: Decomposition problems, which include set-partition, set-cover and set-packing, constitute a core subject in Operations Research. We study NP-hard planar geometric variants of these problems and present integer linear programming (ILP) models and heuristics for them. We also lay the groundwork for further investigations with novel algorithms, data structures, and publicly available benchmarks. Firstly, we study the Minimum Convex Partition of Point Sets, where the goal is to partition the convex hull of a point set P into a minimum number of empty (with no points of P in their interior) convex polygons whose vertex set is P. We propose a graph-based and an arrangement-based ILP model for this problem. For the arrangement-based model, we provide an efficient column generation implementation, together with heuristics, preprocessing and geometry-based branching rules. We identify a small subset of faces of the arrangement, i.e., constraints, that suffice to express the model, as well as a data structure that enables fast queries on sums of dual variables associated to them. Secondly, we investigate the Convex Quadrangulation of Bichromatic Point Sets with Minimum Flips. In this problem, given a bichromatic point set P, one is asked to find the minimum number of color flips that allows the convex hull of P to be partitioned into empty convex quadrangles whose vertex set is P, and whose edges have endpoints of different colors. We introduce a graph-based and an arrangement-based ILP model for this problem. The second model is a novel approach that allows us to express coloring and space partitioning as a compact set-partition model. We use this model to derive heuristics analogue to matching approaches from the literature. Thirdly, we study the Coarseness problem where, given a bichromatic point set P, one seeks to partition P using convex polygons while maximizing the minimum difference between the number of points of each color covered by each polygon. We describe an ILP model with an exponential number of variables that is efficiently implemented using column generation. We combine the relaxation of this model with a heuristic from the literature leading to a polynomial-time iterative preprocessing algorithm. This algorithm solved to proven optimality a large portion of our benchmark. Lastly, we investigated a wireless network inspired set cover problem, called Minimum 3-Colorable Discrete Unit Disk Cover, where, given a point set P and a set D of disks of the same radius, one is asked to find a minimum cover for the points of P using a subset of D that can be colored with at most 3 colors. We describe an ILP model and show how it can be extended and implemented iteratively using Logic-based Benders Decomposition. This decomposition has a set-cover master problem and a 3-coloring subproblem. We prove that the solution of its first iteration uses at most 18 times the minimum number of colors from among all covers of P that use disks in D. We also present graph-theoretical and geometric algorithms to derive stronger cuts that significantly reduce the running time Doutorado Ciência da Computação Doutor em Ciência da Computação FAPESP 2018/14883-5

El presente artículo describe el desarrollo de estructuras desplegables, presentando un caso de estudio realizado como prototipo a escala real, apoyado en el diseño computacional y la fabricación digital: el Pabellón Vértex en el campus de la universidad de Monterrey, Méjico. Para la construcción del mismo se han utilizado principalmente barras de madera, tubos de PVC y cubiertas textiles. El caso de estudio presentado es uno de los realizados en el marco de la investigación y tesis doctoral de Omar Avellaneda, miembro y co-fundador del grupo de investigación SMiA.

Orientador: Hélio Pedrini Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Inicialmente centralizadas na solução de problemas científicos em Dinâmica dos Fluidos, as interfaces evolutivas, com o advento da modelagem mais eficiente e robusta provida pelo método Level Set, expandiram os seus limites originais de aplicabilidade, proporcionando uma nova frente de pesquisa para os campos dos mais diversos, com destaque à Ciência da Computação. Especificamente à área de Processamento de Imagens, os trabalhos até então apresentados, relacionando o Level Set à reconstrução de superfícies tridimensionais, concentram-se na reconstrução a partir de uma nuvem de dados dispersos no espaço; a abordagem baseada em fatias planas paralelas e transversais ao objeto a ser reconstruído evidencia-se ainda incipiente. Esse cenário fomenta, portanto, uma análise da viabilidade do Level Set para a reconstrução de superfícies tridimensionais. Fundamentando-se nessa constatação, a dissertação propõe-se a oferecer uma metodologia que agregue, simultaneamente, as idéias comprovadamente eficientes já publicadas sobre a aproximação em questão e as propostas para contornar as limitações inerentes ao método ainda não satisfatoriamente tratadas, em particular a suavização excessiva de características finas dos contornos em evolução sob o Level Set. Relativamente a esse ponto, o emprego da variante Particle Level Set é sugerido como uma possível solução, por sua intrínseca capacidade comprovada para a conservação de massa ou volume de fronteiras dinâmicas traduzirem-se, presumivelmente, em um controle ao problema destacado. Ao final, conjuntos de dados sintéticos e reais são utilizados para avaliar a metodologia de reconstrução de superfícies tridimensionais apresentada qualitativamente Abstract: Evolving interfaces were initially focused on solutions to scientific problems in Fluid Dynamics. With the advent of the more efficient and robust modeling provided by Level Set method, their original boundaries of applicability were extended, offering a new front of research to the more diverse fields, especially to Computer Science. Specifically to Image Processing area, the works published until then, relating Level Set to tridimensional surface reconstruction, centered themselves on reconstruction from a data cloud dispersed in space; the approach based on parallel planar slices transversal to the object to be reconstructed is still incipient. Therefore, this scenario foments a feasibility analysis of Level Set to the reconstruction of tridimensional surfaces. Basing on this fact, this dissertation proposes to offer a methodology that simultaneously integrates the proved efficient ideas already published about such approximation and the proposals to process the inherent limitations of the method not satisfactorily treated yet, in particular the excessive smoothing of fine characteristics of contours evolving under Level Set. In relation to this, the application of the variant Particle Level Set is suggested as a possible solution, for its intrinsic proved capability to preserve mass or volume of dynamic fronts manifests itself, presumably, into a control of the stressed problem. At the end, synthetic and real data sets are used to evaluate the presented tridimensional surface reconstruction methodology qualitatively Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Eduardo Candido Xavier Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O resumo poderá ser visualizado no texto completo da tese digital Abstract: The complete abstract is available with the full electronic document Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Pedro Jussieu de Rezende Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Problemas de natureza geométrica são encontrados em diversas áreas e, portanto, a análise dos mesmos sob uma ótica algorítmica e imprescindível. Não obstante um amplo tratamento de problemas na geometria euclidiana, relativamente poucos estudos foram feitos em outras geometrias. Em particular, tomando-se como retas sobre o plano as curvas de uma família F que satisfaçam um pequeno conjunto de propriedades, pode-se definir uma geometria de curvas, denotada por GF, a qual foi inicialmente estudada, sob o ponto de vista algorítmico, por Harada [Har00]. Nesta dissertação, estudamos características de famílias de curvas que podem formar uma geometria GF, e sobre ela, primitivas e algoritmos para soluções de problemas. Desenvolvemos ainda um visualizador gráfico, denominado GFViewer, através do qual é possível aprimorar a intuição quanto à forma de construções geométricas, como GF-retas, GF-segmentos, GF-polígonos, GF-bissetores, GF-circunferências, etc. Esse visualizador foi utilizado para testarmos a implementação de alguns algoritmos geométricos sobre certas instâncias de GF. Com a caracterização de algumas famílias de curvas, foi possível construir novos exemplos dessas geometrias. Além disso, na análise dos problemas formulados, verificamos ser plausível a adaptação de algoritmos existentes no caso euclidiano, devido à correlação entre as duas geometrias, de diversas primitivas e predicados Abstract: Problems of geometric nature are found in many areas, so their study under an algorithmic point of view is indispensable. Even though a vast literature exists on problems for the Euclidian geometry, relatively little has been done on other geometries. In particular, if one takes as lines on the plane the curves of a family F that meet a small set of conditions, one may define a geometry of curves, denoted by GF, which was first studied, under an algorithmic approach, by Harada [Har00]. In this dissertation, we identify characteristics of families of curves that may form a GF geometry, over which we study primitives and algorithms for the solution of geometric problems. We also developed a graphical visualizer, known as GFViewer, through which it is possible to improve the intuition towards the understanding of GF-lines, GFsegments, GF-poligons, GF-bissectors, GF-circles, etc. This visualizer was used to test the implementation of a few geometric algorithms over certain instances of GF. With the characterization of some families of curves, it was possible to build new examples of these geometries. Furthermore, in the analysis of the problems studied, we perceived that it is plausible to adapt algorithms that deal with the euclidian case, due to the correlation between the two geometries, of several primitives and predicates Mestrado Teoria da Computação Mestre em Ciência da Computação

Orientador: Wu Shin-Ting Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação Resumo: A simplificação de linha é a operação da generalização cartográfica que remove os detalhes desnecessários de uma linha, preservando os principais aspectos da sua forma. A simplificação consistente de linha preocupa-se tanto em remover estes detalhes, quanto em gerar um mapa que seja consistente.ao original. Um mapa é dito consistente ao original se possuir a mesma topologia que este e conservar espaçamentos entre os seus objetos. Os trabalhos em simplificação consistente presentes na literatura ainda apresentam diversas limitações, das quais se destacam a aplicabilidade restrita a determinados tipos de objetos, a ineficácia na preservação da topologia em certos casos, a ausência da conservação de espaçamentos e o alto custo computacional. Este trabalho propõe uma nova solução para o problema dá simplificação consistente, procurando contornar estas limitações. Do ponto de vista teórico, ele determina um conjunto de condições que se aplicam a todos os tipos de objetos e garantem a consistência do mapa resultante. Do ponto de vista prático, ele apresenta um algoritmo que, com base nestas condições, é capaz de simplificar consistente e eficientemente as linhas de um mapa. O algoritmo proposto tambem apresenta outras características importantes para a simplificação consistente, tais como a capacidade de produzir de mapas independentes de escala e a invariância do mapa resultante em relação à ordem de processamento dos dados de entrada. Abstract: Line simplification is the cartographic generalization operation that reduces the complexity of a line, while preserving its main shape features. Consistent line simplification involves not only the reduction of the line complexity, but also the consistency between the original and the simplified maps. A map is said to be consistent to the original one, if it preserves the topology and keeps the same proximity relation of the objects. Current works in consistent simplification still present drawbacks, such as the applicability to just certain types of objects, the failure while preserving topology in particular cases, the lack of proximity handling and the high computational cost. To overcome these drawbacks, this work proposes a new way for handling the consistent simplification problem. From the theoretical point of view, it presents a set of conditions applicable to all typesof objects, which guarantees the consistency between the original and simplified maps. From the practical point of view, it presents an algorithm that, based on these conditions, can consistently and efficiently simplify the lines of the original map. The algorithm also presents other important properties to the consistent simplification, such as the capacity of producing scale-independent maps and the ability of yielding the same simplified map for different data arrangements in the original map. Mestrado Engenharia de Computação Mestre em Engenharia Elétrica

Orientadores: Paulo Sollero, Eder Lima de Albuquerque Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica Resumo: Este trabalho apresenta o desenvolvimento de um programa de geração de malhas não estruturadas que serão usadas em análises numéricas pelo método dos elementos de contorno. O método dos elementos de contorno é um dos métodos numéricos de destaque usados atualmente em simulações computacionais. Ele possui algumas características particulares que o tornam mais atrativo em determinados tipos de aplicações, quando comparado com outros métodos numéricos. Dentre essas características, está a vantagem de se discretizar somente o contorno das geometrias para o cálculo da solução aproximada do problema. Isso significa dizer que em casos tridimensionais somente elementos de superfície precisam ser gerados na malha. O gerador de malhas implementado neste trabalho foi desenvolvido para gerar malhas com elementos triangulares-lineares em geometrias tridimensionais compostas por faces planas. A idéia geral consiste em deslocar cada face que compõe a geometria tridimensional para o espaço bidimensional usando-se transformações geométricas e, em seguida, aplicar o algoritmo de triangulação de Delaunay para geração dos elementos. Depois de gerados os elementos, novas transformações geométricas são aplicadas a fim de enviar a face de volta para sua posição original no espaço tridimensional. A continuidade da malha é assegurada promovendo-se a geração dos nós nas arestas antes da geração dos nós no interior das faces. Vários exemplos de malhas em geometrias tridimensionais são apresentados para ilustrar a capacidade do programa desenvolvido e algumas análises numéricas foram feitas para demonstrar a qualidade das malhas em problemas com condições de contorno específicas Abstract: This work presents the development of an unstructured mesh generator to be used in numerical analysis by the boundary element method. The boundary element method is one of the prominence methods recently used in computational simulations. It has some particular characteristics that make it more favorable in certain types of applications, when compared to other numerical methods. Among those characteristics, one is especially important from the mesh generation point of view. It is the fact that, in boundary element method, it is only necessary the discretization of the geometry boundaries. In other words, in three-dimensional cases only surface elements should be generated. The mesh generator implemented in this work has been developed to generate meshes with triangular-linear elements over threedimensional geometries composed by plane faces. The general idea consists of moving each face belonging to the three-dimensional geometry to bi-dimensional space using geometrical transformations and the Delaunay triangulation algorithm for element generation. After element generation, new geometrical transformations are applied in order to send the meshed face back to its original position in three-dimensional space. The continuity of the final mesh is assured by generating the nodes of the edges of the geometry prior to the generation of the nodes in the interior of the face. Several examples of meshes in three-dimensional geometries are presented to illustrate the capabilities of the developed program and some numerical analyses have been performed to show the quality of the meshes in problems with specific boundary conditions Mestrado Mecânica dos Sólidos e Projeto Mecânico Mestre em Engenharia Mecânica

Floorfy es una de las empresas que se dedica a realizar renders tridimensionales de hogares para inmobiliarias. Estos renders se les llama tours virtuales. Este servicio tiene muchas ventajas y facilidades para el usuario. Floorfy cuenta conmigo para realizar un nuevo aplicativo dentro de estos tours virtuales que se basa en amueblar un inmueble mediante modelos tridimensionales, a demás de la posibilidad de cambiar los colores y texturas de los objetos, suelos y paredes que hay en el inmueble. Para ello, también será necesario añadir un catálogo con los modelos y texturas disponibles, a demás de añadir unos controles para que el usuario se pueda manejar bien sobre la nueva herramienta. Esta nueva funcionalidad que ofrecerá Floorfy permite al usuario previsualizar un inmueble amueblado a su gusto antes de una posible adquisición, con la finalidad de hacerse una idea de cómo quedaría con una decoración concreta. Floorfy is one of the companies that is dedicated to making three-dimensional renderings of homes for real estate. These renders are called virtual tours. This service has many advantages and facilities for the user. Floorfy is counting on me to create a new application within these virtual tours that is based on furnishing a property using three-dimensional models, in addition to the possibility of changing the colors and textures of the objects, floors and walls that are in it. To do this, it will also be necessary to add a catalog with the available models and textures, in addition to adding some controls so that the user can handle the new tool well. This new functionality that Floorfy will offer allows the user to preview a property furnished to their liking before a possible acquisition, in order to get an idea of how it would look with a specific decoration. Floorfy és una de les empreses que es dedica a realitzar renders tridimensionals de llars per immobiliàries. Aquests renders se'ls anomena tours virtuals. Aquest servei té molts avantatges i facilitats per a l'usuari. Floorfy compta amb mi per fer un nou aplicatiu dins d'aquests tours virtuals que es basa en moblar un immoble mitjançant models tridimensionals, a més de la possibilitat de canviar els colors i textures dels objectes, terres i parets que hi ha a l'immoble. Per a això, també caldrà afegir un catàleg amb els models i textures disponibles, a més d'afegir uns controls perquè l'usuari es pugui gestionar bé sobre la nova eina. Aquesta nova funcionalitat que oferirà Floorfy permet a l'usuari previsualitzar un immoble moblat al seu gust abans d'una possible adquisició, amb la finalitat de fer-se una idea de com quedaria amb una decoració concreta.

We define a two-dimensional statistical depth function and study two important aspects of it: its robustness and computability. We begin by formally proving that the function is, indeed, a statistical depth function. To achieve this, we introduce a new notion of symmetry for distributions in Rp . We study the robustness through the concept of breakdown point. In terms of computability, we provide an implementable algorithm to calculate the depth contours with temporal complexity Θ(n²) and spatial complexity Θ(n), where n is the size of the data set. As an application of the proposed depth function, we provide a hypothesis test for the independence of two absolutely continuous variables RESUMEN: Definimos una función de profundidad estadística bi-dimensional y estudiamos dos aspectos importantes de la misma: la robustez y la computabilidad. Comenzamos probando formalmente que la función es, de hecho, una función de profundidad estadística. Para conseguirlo, introducimos una nueva noción de simetría para distribuciones en Rp . Estudiamos la robustez a través del concepto de breakdown point. En cuanto a la computabilidad, proporcionamos un algoritmo implementable para calcular los contornos de profundidad con complejidad temporal Θ(n²) y complejidad espacial Θ(n), siendo n el tamaño del conjunto de datos. Como aplicación de la función de profundidad propuesta, proporcionamos un contraste de hipótesis para la independencia de dos variables absolutamente continuas. Grado en Matemáticas

Treballs Finals de Grau en Estadística UB-UPC, Facultat d'Economia i Empresa (UB) i Facultat de Matemàtiques i Estadística (UPC), Curs: 2020-2021, Tutor: Montserrat Guillén Estany, El futbol és un dels esports més aleatoris. Un gol succeeix poques vegades durant els noranta minuts d’un partit, la qual cosa fa que l’atzar estigui present en el resultat final. A més, segons Johan Cruyff un jugador sols té la pilota uns tres/cinc minuts en el transcurs del partit. Com a conseqüència, és important quantificar el rendiment d’un equip independentment del resultat i també el rendiment d’un jugador quan no disposa de la pilota. Per tal d’assolir aquest objectiu, en aquest treball final de grau es presenta un algorisme que quantifica una part del rendiment, l’espai generat en fase ofensiva durant el partit, aquest espai es pot diferenciar tant per jugadors com per parts del camp. A partir d’aquest indicador es pot avaluar el posicionament d’un equip durant el partit, a més identificar bons i mals moments. També es pot identificar aquells jugadors que no s’han ubicat de forma correcta i per tant han generat menys perill. A partir de la diferenciació de l’espai en zones del camp completat amb un mapa de calor, es pot veure en quines s’ha disposat de més espai i si ha estat o no utilitzat. Els dos avantatges principals del mètode que es presenta en el treball són: 1. L’alta eficiència computacional del mètode, la qual cosa permet que sigui interactiu. 2. Proporciona informació sobre tots els jugadors que estan en el camp, independentment de si tenen o no la pilota. Tot i que l’enfocament de l’algorisme ha estat dissenyat com a mesura ofensiva, també es podria aplicar com a mesura defensiva, per identificar els defenses que han minimitzat els espais rivals.

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Considerado uma variação do problema da galeria de arte, o problema do posicionamento de antenas trata do posicionamento do menor número de antenas requerido para determinar se uma pessoa está dentro ou fora da galeria. Uma antena propaga uma chave única dentro de um ângulo específico de transmissão, de modo que o conjunto de chaves recebidas em um dado ponto do plano seja suficiente para decidir se ele pertence ou não ao polígono que representa a galeria. Para verificar esta propriedade de localização, uma fórmula Booleana deve ser produzida junto com o posicionamento de antenas. Dizemos que as antenas estão em posição natural se elas estão localizadas nos vértices ou nas arestas do polígono e transmitindo sinal no ângulo formado pelos lados deste último no ponto onde a antena está posicionada. O problema do posicionamento natural de antenas é NP-difícil. Nesta dissertação, apresentamos um algoritmo exato para resolvê-lo. Para tanto, propomos um modelo inicial de programação linear inteira para o problema que, ao ser computado por um resolvedor comercial, se mostrou capaz de encontrar soluções ótimas de instâncias correspondentes a polígonos com algumas dezenas de vértices. Em seguida, através de estudos de propriedades geométricas, são introduzidas várias melhorias no modelo matemático e também na forma de computá-lo. Como consequência desta pesquisa, desenvolvemos um algoritmo iterativo baseado em programação linear inteira com o qual conseguimos solucionar o problema para instâncias consideravelmente maiores. A eficiência do nosso algoritmo é certificada por resultados experimentais que compreendem as soluções ótimas de 720 instâncias de até 1000 vértices, incluindo polígono com buracos, as quais foram calculadas em menos de seis minutos em um computador desktop padrão Abstract: Considered a variation of the art gallery problem, the wireless localization problem deals with the placement of the smallest number of broadcasting antennas required to determine if someone is inside or outside the gallery. Each antenna propagates a unique key within a certain antenna-specific angle of broadcast, so that the set of keys received at any given point is sufficient to determine whether that point is inside or outside the polygon that represents the gallery. To ascertain this localization property, a Boolean formula must be produced along with the placement of the antennas. We say that the antennas are in natural position if they are located at the vertices or the edges of the polygon and transmitting their signals in the angle formed by the sides of the polygon at the point where the antenna is positioned. The natural wireless localization problem is NP-hard. In this dissertation, we present an exact algorithm to solve it. To this end, we propose an initial integer linear programming model for the problem that, after being computed by a commercial solver, proved to be capable of finding optimal solutions for instances corresponding to polygons with tens of vertices. Then, through studies of geometric properties, several improvements are introduced in the mathematical model and also in the way of computing it. As a result of this research, we develop an iterative algorithm based on integer linear programming with which we can solve the problem for considerably larger instances. The efficiency of our algorithm is certified by experimental results comprising the solutions of 720 instances, including polygon with holes with up to 1000 vertices, in less than six minutes on a standard desktop computer Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientadores: Pedro Jussieu de Rezende, Cid Carvalho de Souza Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta dissertação, apresentamos a primeira abordagem algorítmica e os primeiros resultados experimentais da literatura para tratamento do Problema Cromático Discreto da Galeria de Arte (DCAGP). Trata-se de um problema de natureza geométrica que consiste de uma variante do clássico Problema da Galeria de Arte. Neste, deseja-se encontrar um conjunto de guardas com cardinalidade mínima que consiga vigiar toda uma dada galeria. Já no DCAGP temos por objetivo obter um conjunto de observadores que cubra a galeria e que admita uma coloração válida com o menor número de cores. Uma coloração é válida se dois observadores que veem um mesmo ponto recebem cores distintas. Abordamos a resolução deste problema através de duas abordagens: uma exata e uma heurística. Inicialmente, apresentamos uma heurística primal que fornece limitantes superiores de boa qualidade e, em seguida, um modelo de programação linear inteira para resolução exata do DCAGP. Este método foi capaz de resolver todas as instâncias de um extenso conjunto de galerias, representadas por polígonos simples aleatoriamente gerados, de até 2500 vértices, em menos de um minuto. Já num outro conjunto de instâncias onde a representação inclui polígonos com buracos e polígonos fractais de von Koch com até 800 vértices, o método encontrou soluções comprovadamente ótimas para 80% das instâncias em menos de 30 minutos. No contexto dessas soluções, discutimos o uso de lazy-constraints e de técnicas de fortalecimento do modelo, assim como uma breve análise da dificuldade das instâncias. Reportamos ainda resultados da utilização de relaxação Lagrangiana, para obtenção de bons limitantes, principalmente superiores, e também resultados obtidos por meio de uma variação da técnica relax-and-fix. Finalmente, discutimos um processo de branch-and-price para resolução exata do DCAGP Abstract: In this dissertation, we present the first algorithmic approach and the first experimental results in the literature for solving the Discrete Chromatic Art Gallery Problem (DCAGP). This problem is geometric in nature and consists of a variation of the classic Art Gallery Problem. In the latter, we want to find a minimum cardinality guard set that is able to watch over a given gallery. On the other hand, in the DCAGP, the objective is to find a set of watchers that covers the gallery and admits a valid coloring with a minimum number of colors. A coloring is valid if two watchers that observe a same point are assigned different colors. To solve this problem we apply two approaches: an exact and a heuristic one. Firstly, we present a primal heuristic able to provide good quality upper bounds, and subsequently an integer programming model that yields exact solutions for the DCAGP. This method was able to solve all instances from an extensive set of galleries, represented by randomly generated simple polygons, of up to 2500 vertices, in less than one minute. On another set of instances, where the representation includes polygons with holes and fractal von Koch polygons, with up to 800 vertices, this method found proven optimal solutions for 80% of the instances in less than 30 minutes. In the context of these solutions, we discuss the use of lazy constraints and techniques for strengthening the model, besides a brief analysis of the hardness of the instances. Moreover, we report on results obtained through a Lagrangian relaxation, mainly as a means to obtain good upper bounds, as well as from a variation of the relax-and-fix technique. Lastly, we discuss a branch-and-price process for solving the DCAGP to exactness Mestrado Ciência da Computação Mestre em Ciência da Computação