No description available.

In this thesis, we study foldings of orthogonal polygons into orthogonal polyhedra. The particular problem examined here is whether a paper cutout of an orthogonal polygon with fold lines indicated folds up into a simple orthogonal polyhedron. The folds are orthogonal and the direction of the fold (upward or downward) is also given. We present a polynomial time algorithm to solve this problem. Next we consider the same problem with the exception that the direction of the folds are not given. We prove that this problem is NP-complete. Once it has been determined that a polygon does fold into a polyhedron, we consider some restrictions on the actual folding process, modelling the case when the polyhedron is constructed from a stiff material such as sheet metal. We show an example of a polygon that cannot be folded into a polyhedron if folds can only be executed one at a time. Removing this restriction, we show another polygon that cannot be folded into a polyhedron using rigid material.

In this thesis, we study foldings of orthogonal polygons into orthogonal polyhedra. The particular problem examined here is whether a paper cutout of an orthogonal polygon with fold lines indicated folds up into a simple orthogonal polyhedron. The folds are orthogonal and the direction of the fold (upward or downward) is also given. We present a polynomial time algorithm to solve this problem. Next we consider the same problem with the exception that the direction of the folds are not given. We prove that this problem is NP-complete. Once it has been determined that a polygon does fold into a polyhedron, we consider some restrictions on the actual folding process, modelling the case when the polyhedron is constructed from a stiff material such as sheet metal. We show an example of a polygon that cannot be folded into a polyhedron if folds can only be executed one at a time. Removing this restriction, we show another polygon that cannot be folded into a polyhedron using rigid material.

In magnetic resonance imaging (MRI), sampling methods that lead to incomplete data coverage of k-space are used to accelerate imaging and reduce overall scan time. Non-Cartesian sampling trajectories such as radial, spiral, and random trajectories are employed to facilitate advanced imaging techniques, such as compressed sensing, or to provide more efficient coverage of k-space for a shorter scan period. When k-space is undersampled or unevenly sampled, traditional methods of transforming Fourier data to obtain the desired image, such as the FFT, may no longer be applicable. The Fourier reconstruction of optical interferometer data (FROID) algorithm is a novel reconstruction method developed by A. R. Hajian that has been successful in the field of optical interferometry in reconstructing images from sparsely and unevenly sampled data. It is applicable to cases where the collected data is a Fourier representation of the desired image or spectrum. The framework presented allows for a priori information, such as the positions of the sampled points, to be incorporated into the reconstruction of images. Initially, FROID assumes a guess of the real-valued spectrum or image in the form of an interpolated function and calculates the corresponding integral Fourier transform. Amplitudes are then sampled in the Fourier space at locations corresponding to the acquired measurements to form a model dataset. The guess spectrum or image is then adjusted such that the model dataset in the Fourier space is least squares fitted to measured values. In this thesis, FROID has been adapted and implemented for use in MRI where k-space is the Fourier transform of the desired image. By forming a continuous mapping of the image and modelling data in the Fourier space, a comparison and optimization with respect to data acquired in k-space that is either undersampled or irregularly sampled can be performed as long as the sampling positions are known. To apply FROID to the reconstruction of magnetic resonance images, an appropriate objective function that expresses the desired least squares fit criteria was defined and the model for interpolating Fourier data was extended to include complex values of an image. When an image with two Gaussian functions was tested, FROID was able to reconstruct images from data randomly sampled in k-space and was not restricted to data sampled evenly on a Cartesian grid. An MR image of a bone with complex values was also reconstructed using FROID and the magnitude image was compared to that reconstructed by the FFT. It was found that FROID outperformed the FFT in certain cases even when data were rectilinearly sampled.

In magnetic resonance imaging (MRI), sampling methods that lead to incomplete data coverage of k-space are used to accelerate imaging and reduce overall scan time. Non-Cartesian sampling trajectories such as radial, spiral, and random trajectories are employed to facilitate advanced imaging techniques, such as compressed sensing, or to provide more efficient coverage of k-space for a shorter scan period. When k-space is undersampled or unevenly sampled, traditional methods of transforming Fourier data to obtain the desired image, such as the FFT, may no longer be applicable. The Fourier reconstruction of optical interferometer data (FROID) algorithm is a novel reconstruction method developed by A. R. Hajian that has been successful in the field of optical interferometry in reconstructing images from sparsely and unevenly sampled data. It is applicable to cases where the collected data is a Fourier representation of the desired image or spectrum. The framework presented allows for a priori information, such as the positions of the sampled points, to be incorporated into the reconstruction of images. Initially, FROID assumes a guess of the real-valued spectrum or image in the form of an interpolated function and calculates the corresponding integral Fourier transform. Amplitudes are then sampled in the Fourier space at locations corresponding to the acquired measurements to form a model dataset. The guess spectrum or image is then adjusted such that the model dataset in the Fourier space is least squares fitted to measured values. In this thesis, FROID has been adapted and implemented for use in MRI where k-space is the Fourier transform of the desired image. By forming a continuous mapping of the image and modelling data in the Fourier space, a comparison and optimization with respect to data acquired in k-space that is either undersampled or irregularly sampled can be performed as long as the sampling positions are known. To apply FROID to the reconstruction of magnetic resonance images, an appropriate objective function that expresses the desired least squares fit criteria was defined and the model for interpolating Fourier data was extended to include complex values of an image. When an image with two Gaussian functions was tested, FROID was able to reconstruct images from data randomly sampled in k-space and was not restricted to data sampled evenly on a Cartesian grid. An MR image of a bone with complex values was also reconstructed using FROID and the magnitude image was compared to that reconstructed by the FFT. It was found that FROID outperformed the FFT in certain cases even when data were rectilinearly sampled.

農林水産研究情報センターで作成したPDFファイルを使用している。

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura. / [en] In this dissertation we present a survey about the Steiner problem in the rectilinear metric, illustrating its applications to the VLSI desing. A large number of heurístics already described in literature is studied in details. Moreover, we study the complexity of these heuristics and the quality of their solutions. New results concerning their worst case behavior are stated. We also propose two new heuristics for thew Steiner problem in the rectilinear metric, for which we study the complexity and the quality of the solutions, including the worst case analysis. A large nember of computational experiments was conducted and allowed the comparison of the performances of the heuristics implemented. We conclude from these experiments that, in the average, the solutions obtained by one of the new heuristics are better than the solutions obtained by those alreafy available in the literature.

<p>Computational Fluid Dynamic (CFD) simulations often produce datasets defined over unstructured grids with solid boundaries. Though unstructured grids allow for the flexible representation of this geometry and the refinement of the grid resolution, they suffer from high storage cost, non-trivial spatial queries, and low reconstruction smoothness. Rectilinear grids, in contrast, have a negligible memory footprint and readily support smooth data reconstruction, though with reduced geometric flexibility.</p><p>This thesis is concerned with the creation of accurate reconstruction of large unstructured datasets on rectilinear grids with the capability of representing complex boundaries. We present an efficient method to automatically determine the geometry of a rectilinear grid upon which a low-error data reconstruction can be achieved with a given reconstruction kernel. Using this rectilinear grid, we address the potential ill-posedness of the data fitting problem, as well as the necessary balance between smoothness and accuracy, through a bi-level smoothness regularization. To tackle the computational challenge posed by very large input datasets and high-resolution reconstructions, we propose a block-based approach that allows us to obtain a seamless global approximation solution from a set of independently computed sparse least-squares problems. </p><p></p><p>We endow the approximated rectilinear grid with boundary handling capabilities that allows for accommodating challenging boundaries while supporting high-order reconstruction kernels. Results are presented for several 3D datasets that demonstrate the quality of the visualization results that our reconstruction enables, at a greatly reduced computational and memory cost. Our data representation enjoys all the benefits of conventional rectilinear grids while addressing their fundamental geometric limitations.</p>

The crossing number of a graph 𝐺 is the minimum number of crossings in any drawing of 𝐺 in the plane. The rectilinear crossing number of 𝐺 is the minimum number of crossings in any straight-line drawing of 𝐺. The Fáry-Wagner theorem states that planar graphs have rectilinear crossing number zero. By Wagner’s theorem, that is equivalent to stating that every graph that excludes 𝐾₅ and 𝐾₃,₃ as minors has rectilinear crossing number 0. We are interested in discovering other proper minor-closed families of graphs which admit strong upper bounds on their rectilinear crossing numbers. Unfortunately, it is known that the crossing number of 𝐾₃,ₙ with 𝑛 ≥ 1, which excludes 𝐾₅ as a minor, is quadratic in 𝑛, more specifically Ω(𝑛²). Since every 𝑛-vertex graph in a proper minor closed family has O(𝑛) edges, the rectilinear crossing number of all such graphs is trivially O(𝑛²). In fact, it is not hard to argue that O(𝑛) bound on the crossing number is the best one can hope for general enough proper minor-closed families of graphs and that to achieve O(𝑛) bounds, one has to both exclude a minor and bound the maximum degree of the graphs in the family. In this thesis, we do that for bounded degree graphs that exclude a single-crossing graph as a minor. A single-crossing graph is a graph whose crossing number is at most one. The main result of this thesis states that every graph 𝐺 that does not contain a single-crossing graph as a minor has a rectilinear crossing number O(∆𝑛), where 𝐺 has 𝑛 vertices and maximum degree ∆. This dependence on 𝑛 and ∆ is best possible. Note that each planar graph is a single-crossing graph, as is the complete graph 𝐾₅ and the complete bipartite graph 𝐾₃,₃. Thus, the result applies to 𝐾₅-minor-free graphs, 𝐾₃,₃-minor free graphs, as well as to bounded treewidth graphs. In the case of bounded treewidth graphs, the result improves on the previous best known bound of O(∆² · 𝑛) by Wood and Telle [New York Journal of Mathematics, 2007]. In the case of 𝐾₃,₃-minor free graphs, our result generalizes the result of Dujmovic, Kawarabayashi, Mohar and Wood [SCG 2008].

Esta pesquisa qualitativa buscou a realidade ambiental da produção industrial de malharias selecionadas na região de Monte Sião, em Minas Gerais, quanto a maior ou menor presença de preocupações de produção mais limpa, bem como sua visão em termos de redução do uso de água, de energia, e, especialmente, de resíduos sólidos têxteis. Justificou-se pelas preocupações relacionadas ao meio ambiente e sua preservação que implicam em questões cada vez mais pertinentes e abordadas nos estudos relacionados ao vestuário de moda, tal como o design que está inteiramente conectado às mudanças cotidianas, e interessado na redução de materiais. É neste contexto que se encontra a produção mais limpa (P+L), almejando agregar melhorias no processo ou no produto, buscando soluções por meio da apresentação de alguns processos que norteiam estes caminhos. Em vista disso, foi elaborada uma revisão da literatura especializada em têxtil, moda e cenários ambientais, e foi realizada uma investigação de campo baseada em métodos qualitativos exploratório de pesquisa, utilizando-se de observações diretas e entrevistas semiestruturadas efetuadas junto às malharias. Alguns resultados da investigação sugerem que a realidade ambiental da produção industrial de malharias tenha uma aproximação com a produção mais limpa, sobretudo, em relação ao tratamento dado aos resíduos sólidos têxteis. Na abordagem da pesquisa de campo observaram-se diferenças quanto às ações voltadas para a minimização de água, energia, e a geração de resíduos sólidos têxteis, ao passo que evidenciaram uma preocupação e tratamentos aos mesmos, indicando de certa forma que existe um equilíbrio quanto ao direcionamento do resíduo têxtil e a dedicação no tratamento, sendo um importante ponto de cuidado do polo industrial / This qualitative research sought the environmental reality of some selected industrial knitting production in the region of Monte Sião, in Minas Gerais, regarding the greater or lesser presence of \"cleaner production\" concerns, as well as its vision in terms of reduction of water use, energy, and especially solid textile waste. It has been justified by the environmental concerns and their preservation that imply issues increasingly relevant and addressed in studies related to fashion clothing, such as design that is fully connected to everyday changes, and interested in reducing materials. Cleaner production is found in this context, aiming to add improvements in the process or product, seeking solutions through the presentation of some processes that guide these paths. A review of the literature on textiles, fashion and environmental scenarios and a field research were carried out based on qualitative exploratory research methods, using direct observations and semi-structured interviews accomplished on-site. Some research results suggest that the environmental reality of the industrial production of knitting products is in line with cleaner production, especially in relation to the treatment of solid textile waste. In the field research approach, differences were observed regarding actions aimed at minimizing water, energy, and solid textile waste generation, while showing them a concern and treatments, indicating in a certain way that there is a balance to the direction of the textile waste and the dedication in the treatment, being an important point of care of the industrial pole