Models are important tools for understanding the hydrological processes that govern water transport in the landscape and for prediction at times and places where no observations are available. The degree of trust placed on models, however, should not exceed the quality of the data they are fed with. The overall aim of this thesis was to tune the modeling process to account for the uncertainty in the data, by identifying robust parameter values using methods from computational geometry. The methods were developed and tested on data from the Choluteca River basin in Honduras. Quality control of precipitation and discharge data resulted in a rejection of 22% percent of daily raingage data and the complete removal of one out of the seven discharge stations analyzed. The raingage network was not found sufficient to capture the spatial and temporal variability of precipitation in the Choluteca River basin. The temporal variability of discharge was evaluated through a Monte Carlo assessment of the rating-equation parameter values over a moving time window of stage-discharge measurements. Al hydrometric stations showed considerable temporal variability in the stage-discharge relationship, which was largest for low flows, albeit with no common trend. The problem with limited data quality was addressed by identifying robust model parameter values within the set of well-performing (behavioral) parameter-value vectors with computational-geometry methods. The hypothesis that geometrically deep parameter-value vectors within the behavioral set were hydrologically robust was tested, and verified, using two depth functions. Deep parameter-value vectors tended to perform better than shallow ones, were less sensitive to small changes in their values, and were better suited to temporal transfer. Depth functions rank multidimensional data. Methods to visualize the multivariate distribution of behavioral parameters based on the ranked values were developed. It was shown that, by projecting along a common dimension, the multivariate distribution of behavioral parameters for models of varying complexity could be compared using the proposed visualization tools. This has a potential to aid in the selection of an adequate model structure considering the uncertainty in the data. These methods allowed to quantify observational uncertainties. Geometric methods have only recently begun to be used in hydrology. It was shown that they can be used to identify robust parameter values, and some of their potential uses were highlighted. / Modeller är viktiga verktyg för att förstå de hydrologiska processer som bestämmer vattnets transport i landskapet och för prognoser för tider och platser där det saknas mätdata. Graden av tillit till modeller bör emellertid inte överstiga kvaliteten på de data som de matas med. Det övergripande syftet med denna avhandling var att anpassa modelleringsprocessen så att den tar hänsyn till osäkerheten i data och identifierar robusta parametervärden med hjälp av metoder från beräkningsgeometrin. Metoderna var utvecklade och testades på data från Cholutecaflodens avrinningsområde i Honduras. Kvalitetskontrollen i nederbörds- och vattenföringsdata resulterade i att 22 % av de dagliga nederbördsobservationerna måste kasseras liksom alla data från en av sju analyserade vattenföringsstationer. Observationsnätet för nederbörd befanns otillräckligt för att fånga upp den rumsliga och tidsmässiga variabiliteten i den övre delen av Cholutecaflodens avrinningsområde. Vattenföringens tidsvariation utvärderades med en Monte Carlo-skattning av värdet på parametrarna i avbördningskurvan i ett rörligt tidsfönster av vattenföringsmätningar. Alla vattenföringsstationer uppvisade stor tidsvariation i avbördningskurvan som var störst för låga flöden, dock inte med någon gemensam trend. Problemet med den måttliga datakvaliteten bedömdes med hjälp av robusta modellparametervärden som identifierades med hjälp av beräkningsgeometriska metoder. Hypotesen att djupa parametervärdesuppsättningar var robusta testades och verifierades genom två djupfunktioner. Geometriskt djupa parametervärdesuppsättningar verkade ge bättre hydrologiska resultat än ytliga, var mindre känsliga för små ändringar i parametervärden och var bättre lämpade för förflyttning i tiden. Metoder utvecklades för att visualisera multivariata fördelningar av välpresterande parametrar baserade på de rangordnade värdena. Genom att projicera längs en gemensam dimension, kunde multivariata fördelningar av välpresterande parametrar hos modeller med varierande komplexitet jämföras med hjälp av det föreslagna visualiseringsverktyget. Det har alltså potentialen att bistå vid valet av en adekvat modellstruktur som tar hänsyn till osäkerheten i data. Dessa metoder möjliggjorde kvantifiering av observationsosäkerheter. Geometriska metoder har helt nyligen börjat användas inom hydrologin. I studien demonstrerades att de kan användas för att identifiera robusta parametervärdesuppsättningar och några av metodernas potentiella användningsområden belystes.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-20T13:40:45Z No. of bitstreams: 1 wellingtoncarlosdaconceicao.pdf: 4259949 bytes, checksum: 52410bbb422df8d4e80e7f6956efc71e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-21T13:12:55Z (GMT) No. of bitstreams: 1 wellingtoncarlosdaconceicao.pdf: 4259949 bytes, checksum: 52410bbb422df8d4e80e7f6956efc71e (MD5) / Made available in DSpace on 2017-03-21T13:12:55Z (GMT). No. of bitstreams: 1 wellingtoncarlosdaconceicao.pdf: 4259949 bytes, checksum: 52410bbb422df8d4e80e7f6956efc71e (MD5) Previous issue date: 2016-12-12 / O sistema de produção de energia elétrica brasileiro é um sistema hidrotérmico de grande porte com forte predominância de usinas hidrelétricas. O planejamento e operação do sistema é realizado considerando diversos fatores, tais como, estocasticidade das afluências, usinas hidrelétricas em cascata e acoplamento temporal da operação. A resolução deste tipodeproblemaéfeitaconsiderandodiversoshorizontesdeplanejamento. Oplanejamento da operação de médio prazo compreende um período de 5 anos de estudo, e este período é discretizado em base mensal. O presente trabalho apresenta uma metodologia alternativa para resolução do problema de planejamento da operação de médio prazo de sistemas hidrotérmicos utilizando a Programação Dinâmica Estocástica (PDE) com discretização dointercâmbiodeenergiaentreossubsistemas(PDE-INT).Alémdisso, utiliza-seatécnica de sistemas equivalentes de energia e o algoritmo de fechos convexos (convex hull) para obtenção da função de custo futuro a partir dos pontos obtidos pela PDE-INT. Nesta abordagem, para cálculo da política energética, os subsistemas são considerados isolados, e desta forma, as variáveis que compõem o espaço de estados que são discretizadas são a energia armazenada e o intercâmbio líquido entre os subsistemas. Inicialmente, para análise e avaliação da metodologia proposta na resolução do problema de planejamento hidrotérmico, criou-se um sistema tutorial, composto por dois subsistemas. Em seguida, a metodologia foi utilizada considerando todo o sistema elétrico brasileiro, representado por quatro subsistemas ou submercados. Os resultados mostraram que com a técnica de separação dos subsistemas há uma redução significativa no tempo computacional quando comparados com as técnicas tradicionais que utilizam programação dinâmica. Desta forma, a metodologia proposta pode ser utilizada para uma análise rápida e inicial do caso em estudo, servindo como base para estudos e refinamentos posteriores. / The Brazilian power production system is a large scale hydrothermal system with a strong predominance of hydroelectric power plants. The electric power system operation planning must take into consideration several factors, such as uncertainty of the water inflows, hydroelectric plants in cascade and temporal coupling. This problem is solved considering different planning horizon. The long-term operation planning problem is generally solved by a chain of computational models that consider a period of 5 years ahead with monthly discretization. This work presents an alternative strategy to solve hydrothermalsystemsoperationplanningbyStochasticDynamicProgramming(SDP)with discretization of energy interchange between subsystems (SDP-INT). Under the presented approach, the hydroelectric plants are grouped into energy equivalent subsystems and the expected operation cost functions are modeled by a piecewise linear approximation, by means of the convex hull algorithm. Also, under this methodology, the subsystems are solved isolated, but the net energy interchange (export – import) between subsystems is set as a state variable of the cost function, together with the energy storage Initially, for the analysis and evaluation of the proposed methodology applied on solving the hydrothermalplanningproblem, themethodologyisusedinatutorialsystem, composedof two subsystems. Next, a simulation with the whole Brazilian electrical system considering four subsystems is presented. The results have shown that this subsystems separation technique reduces significantly the computation time when compared with the traditional techniques, demonstrating the effectiveness of the proposed methodology. Thus, the proposed methodology can be used for a fast and initial analysis of the case study, serving as a basis for further studies.

Práce se zabývá detekcí kolizí v 3D simulačním prostoru. V první části jsou popsány nejpoužívanější algoritmy pro detekci, stejně jako některé knihovny hotových řešení. Druhá část práce obsahuje popis testovacího softwaru vytvořeného na základě knihovny OpenGL, včetně popisu důležitých částí. V poslední části práce jsou také prezentovány výsledky testování a porovnání vybraných algoritmů na vytvořených testovacích úlohách.

In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within $2^{\log^{1-1/{(\log\log m)^c}}m}$ in polynomial time for any constant $c < 1/2$, unless $P=NP$, when the given objects are $m$ triangles or convex objects. This shows that Red-Blue Geometric Set Cover is a harder problem than Geometric Set Cover for some class of objects. \item Boxes Class Cover is APX-hard. \end{itemize} We also define MaxRM-3SAT, a restricted version of Max3SAT, and we prove that this problem is APX-hard. This problem might be interesting in its own right.\\ In the distributed setting, we define a new model, the fixed-link model, where each processor has a position on the plane and processors can communicate to each other if and only if there is an edge between them. We motivate the model and study a number of geometric problems in this model. We prove lower bounds on the communication complexity of the problems in the fixed-link model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm in the fixed-link model with $n$ nodes to solve the following problems, when the communication is in the asynchronous KT1 model: \begin{itemize} \item $\Omega(n^2/\log n)$ expected bits of communication are required for solving Diameter, Convex Hull, or Closest Pair, even if the graph has only a linear number of edges. \item $\Omega( min\{n^2,1/\epsilon\})$ expected bits of communications are required for approximating Diameter within a $1-\epsilon$ factor of optimal, even if the graph is planar. \item $\Omega(n^2)$ bits of communications is required for approximating Closest Pair in a graph on an $[n^c] \times [n^c]$ grid, for any constant $c>1+1/(2\lg n)$, within $\frac{n^{c-1/2}}{4}-\epsilon$ factor of optimal, even if the graph is planar. \end{itemize} We also present approximation algorithms in geometric communication networks with $n$ nodes, when the communication is in the asynchronous CONGEST KT1 model: \begin{itemize} \item An $\epsilon$-kernel, and consequently $(1-\epsilon)$-\diamapprox~ and \ep -Approximate Hull with $O(\frac{n}{\sqrt{\epsilon}})$ messages plus the costs of constructing a spanning tree. \item An $\frac{n^c}{\sqrt{\frac{k}{2}}}$-Approximate Closest Pair on an $[n^c] \times [n^c]$ grid , for a constant $c>1/2$, plus the cost of computing a spanning tree, for any $k\leq {n-1}$. \end{itemize} We also define a new version of the two-party communication problem, Path Computation, where two parties communicate through a path. We prove a lower bound on the communication complexity of this problem. / Graduate

Chapter 1 introduces Jensen Inequality and its geometric interpretation. Some useful criteria for checking the convexity of functions are discussed. Many applications in various fields are also included. Chapter 2 deals with Schur Inequality, which can easily solve some problems involved symmetric inequality in three variables. The relationship between Schur Inequality and the roots and the coefficients of a cubic equation is also investigated. Chapter 3 presents Muirhead Inequality which is derived from the concept of majorization. It generalizes the inequality of arithmetic and geometric means. The equivalence of majorization and Muirhead¡¦s condition is illustrated. Two useful tricks for applying Muirhead Inequality are provided. Chapter 4 handles Majorization Inequality which involves Majorization and Schur convexity, two of the most productive concepts in the theory of inequalities. Its applications in elementary symmetric functions, sample variance, entropy and birthday problem are considered.

The present research paper deals with the comparison of static and dynamic data structures: static array, dynamic array, pointers array - class TList (Delphi) and dynamic doubly linked list, created with the help of recursive record.To compare the above mentioned structures, sorting (Bubble) and convex hull creation algorithms (Graham, Endrew) are realized, with the time of their implementation analysed. The algorithm of sorting (Bubble) is realized by four ways: static array, dynamic array, pointers array (class TList) and a dynamic doubly linked list, created with the help of recursive record.The algorithms of convex hull creation (Graham, Endrew) is realized by three ways: static array, dynamic array and pointers array (TList).The research paper also describes the pointers array class TList (Delphi), its properties and methods. The sorting method Sort of this class is compared with the sorting method of a “Bubble”. Using class templates, a universal class MList (C++) was created for work with dynamic linear linked lists.

The thesis deals with stochastic and algebraic aspects of the integer convex hull. In the first part, the intrinsic volumes of the randomized integer convex hull are investigated. In particular, we obtained an exact asymptotic order of the expected intrinsic volumes difference in a smooth convex body and a tight inequality for the expected mean width difference. In the algebraic part, an exact formula for the Bhattacharya function of complete primary monomial ideas in two variables is given. As a consequence, we derive an effective characterization for complete monomial ideals in two variables.

The thesis deals with colors - their representation in digital devices and how to provide the best color preservation accross different devices. In the first part of the work, the knowledge of colors and human vision is briefly summarized. Then color models and color spaces are elaborated, mainly those device independent. Spectrum of colors viewable or printable on a device - the gamut - is different for every device and there's a need of precise reproduction or record of color. That's why the system of color management is described further and especially the gamut mapping approaches and algorithms are mentioned. In the second part of the work, the implementation of how two algorithms of color gamut mapping (HPMINDE, SCLIP) can be implemented in MATLAB is described. In the third and last part of the work, the results of implemented algorithms are presented and discussed. These results are compared to results of commonly used color gamut mapping technique (Adobe Photoshop).