Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 149-154).

Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2008. / M.Phil. in Electronic Technology. Includes bibliographical references (p. 57-58).

In this thesis, we design and develop new approximation algorithms and complexity results for three guarding and partitioning problems on orthogonal polygons; namely, guarding orthogonal polygons using sliding cameras, partitioning orthogonal polygons so as to minimize the stabbing number and guarding orthogonal terrains using vertex guards. We first study a variant of the well-known art gallery problem in which sliding cameras are used to guard the polygon. We consider two versions of this problem: the Minimum- Cardinality Sliding Cameras (MCSC) problem in which we want to guard P with the minimum number of sliding cameras, and the Minimum-Length Sliding Cameras (MLSC) problem in which the goal is to compute a set S of sliding cameras for guarding P so as to minimize the total length of trajectories along which the cameras in S travel. We answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an O(n)-time exact algorithm for the MCSC problem on monotone polygons. We then study a conforming variant of the problem of computing a partition of an orthogonal polygon P into rectangles whose stabbing number is minimum over all such partitions of P. The stabbing number of such a partition is the maximum number of rectangles intersected by any orthogonal line segment inside the polygon. In this thesis, we first give an O(n log n)-time algorithm that solves this problem exactly on histograms. We then show that the problem is NP-hard for orthogonal polygons with holes, providing the first hardness result for this problem. To complement the NP-hardness result, we give a 2-approximation algorithm for the problem on both polygons with and without holes. Finally, we study a variant of the terrain guarding problem on orthogonal terrains in which the objective is to guard the vertices of an orthogonal terrain with the minimum number of vertex guards. We give a linear-time algorithm for this problem under a directed visibility constraint. / February 2016

Submitted by Ricardo Pessoa Dos Santos null (ricopessoa@gmail.com) on 2017-12-14T17:35:33Z No. of bitstreams: 1 Dissertação.pdf: 4489608 bytes, checksum: 2c9d751844c4b178546f2154b0718705 (MD5) / Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2017-12-14T18:53:30Z (GMT) No. of bitstreams: 1 santos_rp_me_sjrp.pdf: 4489608 bytes, checksum: 2c9d751844c4b178546f2154b0718705 (MD5) / Made available in DSpace on 2017-12-14T18:53:30Z (GMT). No. of bitstreams: 1 santos_rp_me_sjrp.pdf: 4489608 bytes, checksum: 2c9d751844c4b178546f2154b0718705 (MD5) Previous issue date: 2017-11-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Iremos apresentar a um grupo de alunos do Ensino Médio da rede pública de Ensino do Estado de São Paulo, o mundialmente conhecido quebra cabeças Sudoku, e realizar com eles várias atividades buscando apresentá-lo como subsídio didático na aprendizagem de conceitos matemáticos importantes, além de proporcionar oportunidades de aprimorar a concentração e o raciocínio lógico. Iremos explorar conceitos matemáticos ocultos por trás de suas linhas, colunas e blocos, partindo de uma das primeiras perguntas que podem ser feitas: Qual é a quantidade total de jogos válidos existentes? Para responde-la, será proposto a realização de diversas atividades, primeiramente com um Shidoku (matriz 4 × 4), em seguida iremos calcular o total desses jogos. O tamanho reduzido dessa grade, facilita os cálculos manuais, permitindo visualizar e compreender o processo utilizado, aproveitando para introduzir o princípio fundamental da contagem. A discussão principal desse trabalho, concentra-se na exploração de um método para se determinar a quantidade de jogos válidos existentes para um Sudoku, e para isso, utilizaremos as demonstrações de Bertrand Felgenhauer e Frazer Jarvis. Também apresentaremos um método capaz de gerar uma grade completa de Sudoku, partindo de uma matriz quadrada de ordem 3, que em seguida, será utilizada para gerar uma solução de Sudoku ortogonal. Finalizando, iremos apresentar e explorar algumas formas diferenciadas para os quebra cabeças Sudoku, mostrando variações no formato dos blocos, no tamanho das grades e uma variação que utiliza formas geométricas em suas pistas (Shapedoku). Como desafio de leitura, pesquisa e aprofundamento, será proposto o problema ainda em aberto do número mínimo de dados iniciais para se ter um jogo válido. Podemos afirmar que um dos objetivos esperados, é que tal atividade venha interferir na concentração e raciocínio, auxiliando nas atividades propostas nesse trabalho e que possam ser utilizadas em outros problemas do cotidiano. / We will present to a group of high school students of the public Education of Sao Paulo state, the world-known puzzle Sudoku, and perform with them several activities seeking to present it as a didactic subsidy in the learning important mathematical concepts, besides opportunities to enhance concentration and logical reasoning. We will explore hidden mathematical concepts behind their lines, columns and blocks, starting from one of the rst questions that can be asked: What is the total number of valid games in existence? To answer this question, it will be proposed to perform several activities, rst with a Shidoku (4 × 4 matrix), then we will calculate the total of these games. The reduced size of this grid facilitates manual calculations, allowing to visualize and understand the process used, taking advantage to introduce the fundamental principle of counting. The main discussion of this paper focuses on the exploration of a method to determine the amount of valid games existing for a Sudoku, and for that, we will use the demonstrations of Bertrand Felgenhauer and Frazer Jarvis. We will also present a method capable of generating a complete Sudoku grid, starting from a square matrix of order 3, which will then be used to generate an orthogonal Sudoku solution. Finally, we will introduce and explore some di erent shapes for the Sudoku puzzle, showing variations in the shape of the blocks, the size of the grids and a variation that uses geometric forms in their tracks (Shapedoku). As a challenge for reading, searching and deepening, the open problem of the minimum number of initial data to have a valid game will be proposed. We can say that one of the expected objectives is that such activity will interfere in concentration and reasoning, helping in the activities proposed in this paper and that can be used in other daily problems. / 3107510001F5

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-19Bitstream added on 2014-06-13T20:27:27Z : No. of bitstreams: 1 lima_maf_me_sjrp.pdf: 528569 bytes, checksum: 3cad2d8f7175d945b2ead7fb45a5c4e1 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O principal objetivo deste trabalho é estudar métodos para construir os numeradores e denominadores parciais da fração contínua que corresponde a duas expansões em série de potências de uma função analítica f(z); em z =0 e em z = 00. / The main purpose of this work is to two series expansions of an analytic function f(z); in z =0 and z =00 simultaneously. Furthermore we considered the case when there are zero coefficients in the series and also whwn there is symmetry in the coefficients of the two series. Some examples are given.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-27Bitstream added on 2014-06-13T18:55:33Z : No. of bitstreams: 1 felix_hm_me_sjrp.pdf: 466258 bytes, checksum: 32a3a8d16827478e36816f3317716601 (MD5) / O estudo da obtenção de fórmulas assintóticas para polinômios ortogonais clássicos foi amplamente desenvolvido por Szegö. Recentemente, a necessidade de obtenção de assintóticas para polinômios, ortogonais com respeito a funções peso variadas, foi renovada devido a novos estudos na teoria de matrizes randômicas. Nestes estudos, uma das principais ferramentas utilizadas é a teoria dos problemas de Riemann-Hilbert, caracterizada pelo método de máxima descida de autoria de Deft e Zhou. Essas novas técnicas também aprimoraram os resultados obtidos por Szegö e outros autores predecessores. O objetivo do presente trabalho é esclarecer a conexão entre as teorias de polinômios ortogonais e problemas de Riemann-Hilbert, demonstrando os passos que devem ser seguidos a fim de se obter assintóticas que valham em qualquer subconjunto compacto do plano complexo. Como aplicação, escolhemos os polinômios ortogonais em [¡1; 1] com respeito a uma função peso modificada de Jacobi. / The study of obtaining asymptotics for Classical Orthogonal Polynomials was vas- tly developed by Szegö. Recently, the need for obtaining asymptotics for polynomials, orthogonal with respect to varied weight functions, was renewed due to new researches in the theory of Random Matrices. In these studies, one of the most important tools used lies in the theory of Riemann-Hilbert problems, enforced by the steepest descent method of Deft and Zhou. These new techniques also have improved the results obtained by Szegö and other previous authors. The main purpose of this work is to explain the connection between the theories of Orthogonal Polynomials and Riemann-Hilbert problems, showing the steps to be followed on the way of finding asymptotics which hold true for any compact subsets of the complex plane. As an application, we choose the polynomials orthogonal on [¡1; 1] with respect to a modified Jacobi weight.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-02-24Bitstream added on 2014-06-13T18:30:55Z : No. of bitstreams: 1 veronese_do_me_sjrp.pdf: 430710 bytes, checksum: 769cae2276392992bc8f2c9eaf54fd4e (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Dentre as diversas fórmulas de quadratura interpolatórias estão aquelas que utilizam em sua construção as propriedades dos polinômios ortogonais Pn, ou ainda dos polinômios similares Bn. Consideramos, aqui, fþormulas de quadratura envolvendo polinôomios em x da forma .n(x, .) = Pn-1(.)Pn(x) - Pn(.)Pn-1(x), e da forma Gn(x, u) = Bn-1(u)Bn(x) - Bn(u)Bn-1(x). Abordamos ainda certas fþormulas de quadratura que visam aproximar a integral de um produto de duas funções k e f sendo k Lebesgue integrþavel e f Riemann integrþavel. O principal objetivo deste trabalho þe analisar propriedades das fþormulas de quadratura utilizando-se .n e obter propriedades anþalogas para o caso onde utiliza-se Gn, bem como estudar o erro e as propriedades de convergência das fórmulas envolvendo k e f. Propriedades dos pesos das fórmulas de quadratura nos diversos casos são analisadas, a convergência das fórmulas associadas a k e f são estudadas mediante determinadas escolhas de pontos. / Among the many well known quadrature formulas one finds those interesting interpolatory quadrature formulas that take advantage of the properties of orthogonal polynomials Pn or similar polynomials Bn. Here, we consider the interpolatory quadrature rules based on the zeros of the polynomials øn(x, î) = Pn.1(î)Pn(x).Pn(î)Pn.1(x), and Gn(x, u) = Bn.1(u)Bn(x) . Bn(u)Bn.1(x) where î and u are arbitrary parameters. One of the objective of this dissertation is to study some of the known properties of quadrature rules based on øn(x, î) and consider the analogous properties of the quadrature rules based on Gn(x, u).We also look at the convergence properties of those quadrature rules that serve to approximate integrals of the product of functions k and f, where k is a Lebesgue integrable function and f needs to be a Riemann integrable function.

Made available in DSpace on 2014-06-11T19:27:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-02-16Bitstream added on 2014-06-13T19:47:36Z : No. of bitstreams: 1 cruz_pa_me_sjrp.pdf: 521140 bytes, checksum: c6ea68d0090a86a72c0e40770bfb2980 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O objetivo principal deste trabalho é estudar o problema de análise de freqüência, utilizando polinômios ortogonais no intervalo [0,1]. Para isto, vimos os polinômios ortogonais no círculo unitário, conhecidos como polinômios de Szego, suas relações com as frações contínuas de Perron-Carathéodory e polinômios para-ortogonais. Estudamos, também, relacões entre polinômios para-ortogonais e polinômios ortogonais no intervalo [-1,1], e como são utilizados em análise de freqüência. / The main purpose of this work is to study the frequency analysis problem using ortho- gonal polynomials on the interval [0,1]. For that, we study the orthogonal polynomials in the unit circle, known as Szeg}o polynomials, relations with the continued fractions of Perron- Carathéodory and para-orthogonal polynomials. We also study the relations between the para-orthogonal polynomials and orthogonal polynomials on the interval [-1,1], and how they are used in the frequency analysis problem.