[pt] Uma reta bissetora divide uma região convexa do plano em duas partes com áreas iguais. É natural estudar as envoltórias destas linhas bissetoras, que em geral apresentam singularidades. O caso de polígonos é particularmente interessante, pois existem diversas noções distintas de envoltórias discretas. Nesta dissertação, nós estudamos três tipos diferentes de envoltórias discretas de retas bissetoras e as conexões entre elas. / [en] A bisection line divide a convex planar region into two parts with equal areas. It is natural to study the envelope of these lines, which in general present singularities. The polygonal case is particularly interesting, since there are several different notions of a discrete envelope. In this dissertation, we study three different notions of discrete envelopes of bisection lines and the connections between them.

In the area of Discrete Event Systems (DES), formal verification techniques are important in examining a variety of system properties including controllability and nonblocking. Nonetheless, in reality, most software and hardware practitioners are not proficient in formal methods which holds them back from the formal representation and verification of their systems. Alternatively, it is a common observation that control engineers are typically familiar with Moore synchronous Finite State Machines (FSM) and use them to express their controllers’ behaviour. Taking this into consideration, we devise a generic and structured approach to automatically translate Moore synchronous FSM into timed DES (TDES) supervisors. In this thesis, we describe our FSM-TDES translation method, present a set of algorithms to realize the translation steps and rules, and demonstrate the application and correctness of our translation approach with the help of an example. In order to develop our automatic FSM-TDES translation approach, we exploit the structural similarity created by the sampled-data (SD) supervisory control theory between the two models. To build upon the SD framework, first we address a related issue of disabling the tick event in order to force an eligible prohibitable event in the SD framework. To do this, we introduce a new synchronization operator called the SD synchronous product (||SD), adapt the existing TDES and SD properties, and devise our ||SD setting. We formally verify the controllability and nonblocking properties of our ||SD setting by establishing logical equivalence between the existing SD setting and our ||SD setting. We present algorithms to implement our ||SD setting in the DES research tool, DESpot. The formulation of the ||SD operator provides twofold benefits. First, it simplifies the design logic of the TDES supervisors that are modelled in the SD framework. This results in improving the ease of manually designing SD controllable TDES supervisors, and reduced verification time of the closed-loop system. We demonstrate these benefits by applying our ||SD setting to an example system. Second, it bridges the gap between theoretical supervisors and physical controllers with respect to event forcing. This makes our FSM-TDES translation approach relatively uncomplicated. Our automatic FSM-TDES translation approach enables the designers to obtain a formal representation of their controllers without designing TDES supervisors by hand and without requiring formal methods expertise. Overall, this work should increase the adoption of the SD supervisory control theory in particular, and formal methods in general, in the industry by facilitating software and hardware practitioners in the formal representation and verification of their control systems. / Dissertation / Doctor of Philosophy (PhD)

No description available.

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)

Systems biology is an emergent field focused on developing a system-level understanding of biological systems. In the last decade advances in genomics, transcriptomics and proteomics have gathered a remarkable amount data enabling the possibility of a system-level analysis to be grounded at a molecular level. The reverse-engineering of biochemical networks from experimental data has become a central focus in systems biology. A variety of methods have been proposed for the study and identification of the system's structure and/or dynamics. The objective of this dissertation is to introduce and propose solutions to some of the challenges inherent in reverse-engineering of biological systems. First, previously developed reverse engineering algorithms are studied and compared using data from a simulated network. This study draws attention to the necessity for a uniform benchmark that enables an ob jective comparison and performance evaluation of reverse engineering methods. Since several reverse-engineering algorithms require discrete data as input (e.g. dynamic Bayesian network methods, Boolean networks), discretization methods are being used for this purpose. Through a comparison of the performance of two network inference algorithms that use discrete data (from several different discretization methods) in this work, it has been shown that data discretization is an important step in applying network inference methods to experimental data. Next, a reverse-engineering algorithm is proposed within the framework of polynomial dynamical systems over finite fields. This algorithm is built for the identification of the underlying network structure and dynamics; it uses as input gene expression data and, when available, a priori knowledge of the system. An evolutionary algorithm is used as the heuristic search method for an exploration of the solution space. Computational algebra tools delimit the search space, enabling also a description of model complexity. The performance and robustness of the algorithm are explored via an artificial network of the segment polarity genes in the D. melanogaster. Once a mathematical model has been built, it can be used to run simulations of the biological system under study. Comparison of simulated dynamics with experimental measurements can help refine the model or provide insight into qualitative properties of the systems dynamical behavior. Within this work, we propose an efficient algorithm to describe the phase space, in particular to compute the number and length of all limit cycles of linear systems over a general finite field. This research has been partially supported by NIH Grant Nr. RO1GM068947-01. / Ph. D.

The task of detecting human faces within either a still image or a video frame is one of the most popular object detection problems. For the last twenty years researchers have shown great interest in this problem because it is an essential pre-processing stage for computing systems that process human faces as input data. Example applications include face recognition systems, vision systems for autonomous robots, human computer interaction systems (HCI), surveillance systems, biometric based authentication systems, video transmission and video compression systems, and content based image retrieval systems. In this thesis, non-traditional methods are investigated for detecting human faces within color images or video frames. The attempted methods are chosen such that the required computing power and memory consumption are adequate for real-time hardware implementation. First, a standard color image database is introduced in order to accomplish fair evaluation and benchmarking of face detection and skin segmentation approaches. Next, a new pre-processing scheme based on skin segmentation is presented to prepare the input image for feature extraction. The presented pre-processing scheme requires relatively low computing power and memory needs. Then, several feature extraction techniques are evaluated. This thesis introduces feature extraction based on Two Dimensional Discrete Cosine Transform (2D-DCT), Two Dimensional Discrete Wavelet Transform (2D-DWT), geometrical moment invariants, and edge detection. It also attempts to construct a hybrid feature vector by the fusion between 2D-DCT coefficients and edge information, as well as the fusion between 2D-DWT coefficients and geometrical moments. A self organizing map (SOM) based classifier is used within all the experiments to distinguish between facial and non-facial samples. Two strategies are tried to make the final decision from the output of a single SOM or multiple SOM. Finally, an FPGA based framework that implements the presented techniques, is presented as well as a partial implementation. Every presented technique has been evaluated consistently using the same dataset. The experiments show very promising results. The highest detection rate of 89.2% was obtained when using a fusion between DCT coefficients and edge information to construct the feature vector. A second highest rate of 88.7% was achieved by using a fusion between DWT coefficients and geometrical moments. Finally, a third highest rate of 85.2% was obtained by calculating the moments of edges. / Master of Science

The High Occupancy Vehicle (HOV) lanes on Atlanta, Georgia’s radial I-85 had long been providing sub-optimal throughput in the peak traffic hours, as the two-person occupancy requirement allowed the lanes to become heavily congested. The Georgia Department of Transportation converted 15.5 miles of HOV 2+ lanes to High Occupancy Toll (HOT) lanes, one in each direction on I-85. The lanes use dynamic value pricing to set toll levels based on the volume and average speed of traffic in the lanes. The goal of this research was to investigate the responses to toll lane pricing and the factors that appear to inform lane choice decisions, as well as examining values of travel time savings and toll price elasticity for users of the Express Lanes. This study of the metropolitan Atlanta I-85 Express Lanes operates at the microscopic level to examine the impact of demographic characteristics, congestion levels, and pricing on users’ decisions to use or not use the I-85 Express Lanes. The dissertation examined the value of travel time savings distributions across income segments. The differences in these distributions among lower, medium, and higher income households were marginal at best. The results did not indicate that higher income households had the highest value of travel time savings results, as may have been expected. The modeling work performed here provided a number of insights into toll lane use. The determinants of lane choice decision-making in the morning peak had notable differences from the determinants of the afternoon peak. The initial analysis involved models which were estimated across three different income segments to examine differences in decision making between low, medium, and higher income households. The results indicated that the parameters were largely consistent across the three segments. Further segmenting the households showed that lane choice determinants varied more within the ‘Higher’ income segment than across the original three-segment structure. In particular, the five-segment models illustrated lower elasticities with regard to corridor segment counts and toll levels for the highest-income households in the sample, as well as higher household income level elasticities for afternoon trips by that same cohort. The research was among the first in the available literature to use revealed preference lane use data for both the toll lane users and the unpriced general purpose lane users. The use of household level marketing data, rather than census or survey data, was another unique characteristic of this research. The analysis of value of travel time savings with a demographic component that looks at household income has not yet been seen in the literature; similarly, the findings regarding differing behavior among very high income households appear to be unseen in the existing literature. The results from this analysis, such as willingness-to-pay values for different population segments, will be useful inputs to the decisions surrounding future HOT implementations in the Atlanta region. The use of new data sources, the evaluation of those types of data sources, and the application of methods that have previously been unused in this field make up the primary contributions of this dissertation.

The study of the shear behavior of particulate (soil) – continuum (man-made material) interfaces has received significant attention during the last three decades. The historical belief that the particulate – continuum interface represents the weak link in most geotechnical systems has been shown to be incorrect for many situations. Namely, prescribing properties of the continuum material, such as its surface roughness and hardness, can result in interface strengths that are equal to the contacting soil mass internal shear strength. This research expands the engineering implications of these findings by studying the response of interface systems in different loading conditions. Specifically, the axial and torsional shear modes are studied in detail. Throughout this thesis it is shown that taking an engineering approach to design the loading conditions induced to the interface system can result in interface strengths that exceed the previously considered limiting shear strength of the contacting soil. Fundamental experimental and numerical studies on specimens of different types of sand subjected to torsional and axial interface shear highlighted the inherent differences of these processes. Specifically, micro-scale soil deformation measurements showed that torsional shear induces larger soil deformations as compared to axial shear, as well as complex volume-change tendencies consisting of dilation and contraction in the primary and secondary shear zones. Studies on the global response of torsional and axial shear tests showed that they are affected differently by soil properties such as particle angularity and roughness. This difference in global behavior highlights the benefits of making systems that transfer load to the contacting soil in different manners available for use in geotechnical engineering. Discrete Element Modeling (DEM) simulations allowed for internal information of the specimens to be studied, such as their fabric and shear-induced loading conditions. These findings allowed for the development of links between the measured micro-scale behavior and the observed global-scale response. The understanding of the behavior of torsional and axial interfaces has allowed provides a framework for the development of enhanced geotechnical systems and applications. The global response of torsional shear found to induce larger cyclic contractive tendencies within the contacting soil mass. Therefore, this shear mode is more desirable than the conventional axial shear for the study of phenomena that depend on soil contractive behavior, such as liquefaction. A study on the influence of surface roughness form revealed that surfaces with periodic profiles of protruding elements that prevent clogging are capable of mobilizing interface friction angles that are 20 to 60% larger than the soil friction angle. These findings have direct implications in engineering design since their implementation can result in more resilient and sustainable geotechnical systems.

Doctor of Philosophy / Department of Physics / Christopher M. Sorensen / This work presents a microphysical model of the classical interaction of electromagnetic waves with arbitrary single and multiple particles. The model is based on the volume integral equation solution to the macroscopic time-harmonic Maxwell equations. The integral is discretized over a particle's volume. The near and far-field scattered wave is then described by the secondary radiation from the discretized elements. The physical origin of the angular structure of the scattered wave is characterized by the superposition of these secondary waves. A graphical technique is developed to visualize how this superposition relates to the physical features of a particle, e.g., its size, shape, and refractive index. Numerical and analytical implementations of the model are presented for spherical and spheroidal particles and fractal-like spherical-particle aggregates. The connection between the reflection symmetry of a particle and the polarization state of its far-field scattered wave is illustrated. The model is used to explain the cause of the angular power-law patterns in a particle's scattered intensity. An analysis of the internal field distribution in fractal-like aggregates is performed and the results are compared to the Rayleigh-Debye-Gans theory. Extinction and the optical theorem are examined within the context of the model, resulting in a new understanding for the physical mechanism causing extinction and implications regarding its measurement. The culmination of this work is the unification of multiple scattering-concepts, often regarded as distinct, and the resulting insight afforded by the unified microphysical picture. This unified view is shown to reveal a new and simple explanation for the famous extinction paradox.

Doctor of Philosophy / Department of Biological & Agricultural Engineering / Mark E. Casada / Ronaldo G. Maghirang / The United States grain handling infrastructure is facing major challenges to meet worldwide customer demands for wholesome, quality, and safe grains and oilseeds for food and feed. Several challenges are maintaining grain quality during handling; reducing dust emissions for safety and health issues; growing shift from commodity-based to specialty (trait-specific) markets; proliferation of genetically modified crops for food, feed, fuel, pharmaceutical, and industrial uses; and threats from biological and chemical attacks. This study was conducted to characterize the quality of grain and feed during bucket elevator handling to meet customer demand for high quality and safe products. Specific objectives were to (1) determine the effect of repeated handling on the quality of feed pellets and corn; (2) characterize the dust generated during corn and wheat handling; (3) develop and evaluate particle models for simulating the flow of grain during elevator handling; and (4) accurately simulate grain commingling in elevator boots with discrete element method (DEM). Experiments were conducted at the research elevator of the USDA-ARS Center for Grain and Animal Health Research (CGAHR) to determine the effect of repeated handling on the quality of corn-based feed pellets and corn. Repeated handling did not significantly influence the durability indices of feed pellets and corn. The feed pellets, however, had significantly greater breakage (3.83% per transfer) than the corn (0.382% per transfer). The mass of particulate matter < 125 μm was less for feed pellets than for corn. These corn-based feed pellets can be an alternative to corn in view of their handling characteristics. Another series of experiments was conducted in the same elevator to characterize the dust generated during corn and wheat handling. Dust samples were collected from the lower and upper ducts upstream of the cyclones in the elevator. Handling corn produced more than twice as much total dust than handling wheat (185 g/t vs. 64.6 g/t). Analysis of dust samples with a laser diffraction analyzer showed that the corn samples produced smaller dust particles, and a greater proportion of small particles, than the wheat samples. Published data on material and interaction properties of selected grains and oilseeds that are relevant to DEM modeling were reviewed. Using these material and interaction properties and soybeans as the test material, the DEM fundamentals were validated by modeling the flow of soybean during handling with a commercial software package (EDEM). Soybean kernels were simulated with single- and multi-sphere particle shapes. A single-sphere particle model best simulated soybean kernels in the bulk property tests. The best particle model had a particle coefficient of restitution of 0.6; particle static friction of 0.45 for soybean-soybean contact (0.30 for soybean-steel interaction); particle rolling friction of 0.05; normal particle size distribution with standard deviation factor of 0.4; and particle shear modulus of 1.04 MPa. The single-sphere particle model for soybeans was implemented in EDEM to simulate grain commingling in a pilot-scale bucket elevator boot using 3D and quasi-2D models. Pilot-scale boot experiments of soybean commingling were performed to validate these models. Commingling was initially simulated with a full 3D model. Of the four quasi-2D boot models with reduced control volumes (4d, 5d, 6d, and 7d; i.e., control volume widths from 4 to 7 times the mean particle diameter) considered, the quasi-2D (6d) model predictions best matched those of the initial 3D model. Introduction of realistic vibration motion during the onset of clear soybeans improved the prediction capability of the quasi-2D (6d) model. The physics of the model was refined by accounting for the initial surge of particles and reducing the gap between the bucket cups and the boot wall. Inclusion of the particle surge flow and reduced gap gave the best predictions of commingling of all the tested models. This study showed that grain commingling in a bucket elevator boot system can be simulated in 3D and quasi-2D DEM models and gave results that generally agreed with experimental data. The quasi-2D (6d) models reduced simulation run time by 29% compared to the 3D model. Results of this study will be used to accurately predict impurity levels and improve grain handling, which can help farmers and grain handlers reduce costs during transport and export of grains and make the U.S. grain more competitive in the world market.