Quadratic Time Computable Instances of MaxMin and MinMax Area Triangulations of Convex Polygons

We consider the problems of finding two optimal triangulations of a convex polygon: MaxMin area and MinMax area. These are the triangulations that maximize the area of the smallest area triangle in a triangulation, and respectively minimize the area of the largest area triangle in a triangulation, over all possible triangulations. The problem was originally solved by Klincsek by dynamic programming in cubic time [2]. Later, Keil and Vassilev devised an algorithm that runs in O(n^2 log n) time [1]. In this paper we describe new geometric findings on the structure of MaxMin and MinMax Area triangulations of convex polygons in two dimensions and their algorithmic implications. We improve the algorithm’s running time to quadratic for large classes of convex polygons. We also present experimental results on MaxMin area triangulation.

An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.

An Empirical Evaluation of Preconditioning Data for Accelerating Convex Hull Computations

The convex hull describes the extent or shape of a set of data and is used ubiquitously in computational geometry. Common algorithms to construct the convex hull on a finite set of n points (x,y) range from O(nlogn) time to O(n) time. However, it is often the case that a heuristic procedure is applied to reduce the original set of n points to a set of s < n points which contains the hull and so accelerates the final hull finding procedure. We present an algorithm to precondition data before building a 2D convex hull with integer coordinates, with three distinct advantages. First, for all practical purposes, it is linear; second, no explicit sorting of data is required and third, the reduced set of s points is constructed such that it forms an ordered set that can be directly pipelined into an O(n) time convex hull algorithm. Under these criteria a fast (or O(n)) pre-conditioner in principle creates a fast convex hull (approximately O(n)) for an arbitrary set of points. The paper empirically evaluates and quantifies the acceleration generated by the method against the most common convex hull algorithms. An extra acceleration of at least four times when compared to previous existing preconditioning methods is found from experiments on a dataset.

Expanding the Design Space: Forging the Transition from 3D Printing to Additive Manufacturing

Thesis (Master's)--University of Washington, 2016-08

Efficient algorithms for beacon routing in polygons

In a paper by Biro et al. [7], a novel twist on guarding in art galleries is introduced. A beacon is a fixed point with an attraction pull that can move points within the polygon. Points move greedily to monotonically decrease their Euclidean distance to the beacon by moving straight towards the beacon or sliding on the edges of the polygon. The beacon attracts a point if the point eventually reaches the beacon. Unlike most variations of the art gallery problem, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. For a given point in the polygon, the inverse attraction region is the set of beacon locations that can attract the point. We first study the characteristics of beacon attraction. We consider the quality of a "successful" beacon attraction and provide an upper bound of $\sqrt{2}$ on the ratio between the length of the beacon trajectory and the length of the geodesic distance in a simple polygon. In addition, we provide an example of a polygon with holes in which this ratio is unbounded. Next we consider the problem of computing the shortest beacon watchtower in a polygonal terrain and present an $O(n \log n)$ time algorithm to solve this problem. In doing this, we introduce $O(n \log n)$ time algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. We also prove that $\Omega(n \log n)$ time is a lower bound for computing the beacon kernel of a monotone polygon. Finally, we study the inverse attraction region of a point in a simple polygon. We present algorithms to efficiently compute the inverse attraction region of a point for simple, monotone, and terrain polygons with respective time complexities $O(n^2)$, $O(n \log n)$ and $O(n)$. We show that the inverse attraction region of a point in a simple polygon has linear complexity and the problem of computing the inverse attraction region has a lower bound of $\Omega(n \log n)$ in monotone polygons and consequently in simple polygons.

Geometrical Methods in Multivariate Risk Management: Algorithms and Applications

This thesis builds a framework for evaluating downside risk from multivariate data via a special class of risk measures (RM). The peculiarity of the analysis lies in getting rid of strong data distributional assumptions and in orientation towards the most critical data in risk management: those with asymmetries and heavy tails. At the same time, under typical assumptions, such as the ellipticity of the data probability distribution, the conformity with classical methods is shown. The constructed class of RM is a multivariate generalization of the coherent distortion RM, which possess valuable properties for a risk manager. The design of the framework is twofold. The first part contains new computational geometry methods for the high-dimensional data. The developed algorithms demonstrate computability of geometrical concepts used for constructing the RM. These concepts bring visuality and simplify interpretation of the RM. The second part develops models for applying the framework to actual problems. The spectrum of applications varies from robust portfolio selection up to broader spheres, such as stochastic conic optimization with risk constraints or supervised machine learning.

Computational Method to Determine Reflected Ultrasonic Signals From Arbitrary-Geometry Targets

A computational method based on the impulse response and on the discrete representation computational concept is proposed for the determination of the echo responses from arbitrary-geometry targets. It is supposed that each point of the transducer aperture can be considered as a source radiating hemispherical waves to the reflector. The local interaction with each of the hemispherical waves at the reflector surface can be modeled as a plane wave impinging on a planar surface, using the respective reflection coefficient. The method is valid for all field regions and can be performed for any excitation waveform radiated from an arbitrary acoustic aperture. The effects of target geometry, position, and material on both the amplitude and the shape of the echo response are studied. The model is compared with experimental results obtained using broadband transducers together with plane and cylindrical concave rectangular reflectors (aluminum, brass, and acrylic), as well as a circular cavity placed on a plane surface, in a water medium. The method can predict the measured echoes accurately. This paper shows an improved approach of the method, considering the reflection coefficient for all incident hemispherical waves arriving at each point of the target surface.

Computational tool for three-point hitch geometry optimization

The weight-transfer effect, consisting of the change in dynamic load distribution between the front and the rear tractor axles, is one of the most impairing phenomena for the performance, comfort, and safety of agricultural operations. Excessive weight transfer from the front to the rear tractor axle can occur during operation or maneuvering of implements connected to the tractor through the three-point hitch (TPH). In this respect, an optimal design of the TPH can ensure better dynamic load distribution and ultimately improve operational performance, comfort, and safety. In this study, a computational design tool (The Optimizer) for the determination of a TPH geometry that minimizes the weight-transfer effect is developed. The Optimizer is based on a constrained minimization algorithm. The objective function to be minimized is related to the tractor front-to-rear axle load transfer during a simulated reference maneuver performed with a reference implement on a reference soil. Simulations are based on a 3-degrees-of-freedom (DOF) dynamic model of the tractor-TPH-implement aggregate. The inertial, elastic, and viscous parameters of the dynamic model were successfully determined through a parameter identification algorithm. The geometry determined by the Optimizer complies with the ISO-730 Standard functional requirements and other design requirements. The interaction between the soil and the implement during the simulated reference maneuver was successfully validated against experimental data. Simulation results show that the adopted reference maneuver is effective in triggering the weight-transfer effect, with the front axle load exhibiting a peak-to-peak value of 27.1 kN during the maneuver. A benchmark test was conducted starting from four geometries of a commercially available TPH. As result, all the configurations were optimized by above 10%. The Optimizer, after 36 iterations, was able to find an optimized TPH geometry which allows to reduce the weight-transfer effect by 14.9%.

Reactivity, photolability, and computational studies of the ruthenium nitrosyl complex with a substituted cyclam fac-[Ru(NO)Cl(2)(kappa(3)N(4),N(8),N(11)(1-carboxypropyl)cyclam)]Cl center dot H(2)O

Chemical reactivity, photolability, and computational studies of the ruthenium nitrosyl complex with a substituted cyclam, fac-[Ru(NO)Cl(2)(kappa(3)N(4),N(8),N(11)(1-carboxypropyl)cyclam)]Cl center dot H(2)O ((1-carboxypropyl) cyclam = 3-(1,4,8,11-tetraazacyclotetradecan-1-yl) propionic acid)), (I) are described. Chloride ligands do not undergo aquation reactions (at 25 degrees C, pH 3). The rate of nitric oxide (NO) dissociation (k(obs-NO)) upon reduction of I is 2.8 s(-1) at 25 +/- 1 degrees C (in 0.5 mol L(-1) HCl), which is close to the highest value found for related complexes. The uncoordinated carboxyl of I has a pK(a) of similar to 3.3, which is close to that of the carboxyl of the non coordinated (1-carboxypropyl) cyclam (pK(a) = 3.4). Two additional pK(a) values were found for I at similar to 8.0 and similar to 11.5. Upon electrochemical reduction or under irradiation with light (lambda(irr) = 350 or 520 nm; pH 7.4), I releases NO in aqueous solution. The cyclam ring N bound to the carboxypropyl group is not coordinated, resulting in a fac configuration that affects the properties and chemical reactivities of I, especially as NO donor, compared with analogous trans complexes. Among the computational models tested, the B3LYP/ECP28MDF, cc-pVDZ resulted in smaller errors for the geometry of I. The computational data helped clarify the experimental acid-base equilibria and indicated the most favourable site for the second deprotonation, which follows that of the carboxyl group. Furthermore, it showed that by changing the pH it is possible to modulate the electron density of I with deprotonation. The calculated NO bond length and the Ru/NO charge ratio indicated that the predominant canonical structure is [Ru(III)NO], but the Ru-NO bond angles and bond index (b.i.) values were less clear; the angles suggested that [Ru(II)NO(+)] could contribute to the electronic structure of I and b.i. values indicated a contribution from [Ru(IV)NO(-)]. Considering that some experimental data are consistent with a [Ru(II)NO(+)] description, while others are in agreement with [Ru(III)NO], the best description for I would be a linear combination of the three canonical forms, with a higher weight for [Ru(II)NO(+)] and [Ru(III)NO].

Two dimensional computational fluid dynamic models for waste stabilisation ponds

Traditional waste stabilisation pond (WSP) models encounter problems predicting pond performance because they cannot account for the influence of pond features, such as inlet structure or pond geometry, on fluid hydrodynamics. In this study, two dimensional (2-D) computational fluid dynamics (CFD) models were compared to experimental residence time distributions (RTD) from literature. In one of the-three geometries simulated, the 2-D CFD model successfully predicted the experimental RTD. However, flow patterns in the other two geometries were not well described due to the difficulty of representing the three dimensional (3-D) experimental inlet in the 2-D CFD model, and the sensitivity of the model results to the assumptions used to characterise the inlet. Neither a velocity similarity nor geometric similarity approach to inlet representation in 2-D gave results correlating with experimental data. However. it was shown that 2-D CFD models were not affected by changes in values of model parameters which are difficult to predict, particularly the turbulent inlet conditions. This work suggests that 2-D CFD models cannot be used a priori to give an adequate description of the hydrodynamic patterns in WSP. (C) 1998 Elsevier Science Ltd. All rights reserved.

Drilling tool geometry evaluation for reinforced composite laminates

In this work, a comparative study on different drill point geometries and feed rate for composite laminates drilling is presented. For this goal, thrust force monitoring during drilling, hole wall roughness measurement and delamination extension assessment after drilling is accomplished. Delamination is evaluated using enhanced radiography combined with a dedicated computational platform that integrates algorithms of image processing and analysis. An experimental procedure was planned and consequences were evaluated. Results show that a cautious combination of the factors involved, like drill tip geometry or feed rate, can promote the reduction of delamination damage.

Phex: a computational tool for plate heat exchanges design problems

This paper presents a computational tool (PHEx) developed in Excel VBA for solving sizing and rating design problems involving Chevron type plate heat exchangers (PHE) with 1-pass-1-pass configuration. The rating methodology procedure used in the program is outlined, and a case study is presented with the purpose to show how the program can be used to develop sensitivity analysis to several dimensional parameters of PHE and to observe their effect on transferred heat and pressure drop.

Experimental and computational study on the synthesis and characterization of self-assembling meso/macroporous materials in highly concentrated emulsions

Report for the scientific sojourn carried out at Massachusetts General Hospital Cancer Center-Harvard Medical School, Estats Units, from 2010 to 2011. The project aims to study the aggregation behavior of amphiphilic molecules in the continuous phase of highly concentrated emulsions, which can be used as templates for the synthesis of meso/macroporous materials. At this stage of the project, we have investigated the self-assembly of diblock and triblock surfactants under the effect of a confined geometry being surrounded by the droplets of the dispersed phase. These droplets limit the growth of the aggregates, deeply modify their orientation and hence alter their spatial arrangement as compared to the self-assembly taking place far enough from any boundary surface, that is in the bulk. By performing Monte Carlo simulations, we have showed that the interface between the dispersed and continuous phases as well as its shape has a significant impact on the structural order of the resulting aggregates and hence on the potential applications of highly concentrated emulsions as reaction media, drug delivery systems, or templates for meso/macroporous materials. Due to the combined effect of symmetry breaking and morphological frustration, very intriguing structures, such as square columnar liquid crystals, twisted X-shaped aggregates, and helical phases of cylindrical aggregates, never observed in the bulk for the same model surfactant, have been found. The presence of other more conventional structures, such as micelles and cubic and hexagonal liquid crystals, formed at low and high amphiphilic concentrations, respectively, further enhance the interest on this already rich aggregation behavior.

Computational and Experimental Analysis of Flow Field in the Diffusers of Centrifugal Compressors

Centrifugal compressors are widely used for example in process industry, oil and gas industry, in small gas turbines and turbochargers. In order to achieve lower consumption of energy and operation costs the efficiency of the compressor needs to be improve. In the present work different pinches and low solidity vaned diffusers were utilized in order to improve the efficiency of a medium size centrifugal compressor. In this study, pinch means the decrement of the diffuser flow passage height. First different geometries were analyzed using computational fluid dynamics. The flow solver Finflo was used to solve the flow field. Finflo is a Navier-Stokes solver. The solver is capable to solve compressible, incompressible, steady and unsteady flow fields. Chien's k-e turbulence model was used. One of the numerically investigated pinched diffuser and one low solidity vaned diffuser were studied experimentally. The overall performance of the compressor and the static pressure distribution before and after the diffuser were measured. The flow entering and leaving the diffuser was measured using a three-hole Cobra-probe and Kiel-probes. The pinch and the low solidity vaned diffuser increased the efficiency of the compressor. Highest isentropic efficiency increment obtained was 3\% of the design isentropic efficiency of the original geometry. It was noticed in the numerical results that the pinch made to the hub and the shroud wall was most beneficial to the operation of the compressor. Also the pinch made to the hub was better than the pinchmade to the shroud. The pinch did not affect the operation range of the compressor, but the low solidity vaned diffuser slightly decreased the operation range.The unsteady phenomena in the vaneless diffuser were studied experimentally andnumerically. The unsteady static pressure was measured at the diffuser inlet and outlet, and time-accurate numerical simulation was conducted. The unsteady static pressure showed that most of the pressure variations lay at the passing frequency of every second blade. The pressure variations did not vanish in the diffuser and were visible at the diffuser outlet. However, the amplitude of the pressure variations decreased in the diffuser. The time-accurate calculations showed quite a good agreement with the measured data. Agreement was very good at the design operation point, even though the computational grid was not dense enough inthe volute and in the exit cone. The time-accurate calculation over-predicted the amplitude of the pressure variations at high flow.

Performance Improvement of Centrifugal Compressor Stage with Pinched Geometry or Vaned Diffuser

Centrifugal compressors are widely used for example in refrigeration processes, the oil and gas industry, superchargers, and waste water treatment. In this work, five different vaneless diffusers and six different vaned diffusers are investigated numerically. The vaneless diffusers vary only by their diffuser width, so that four of the geometries have pinch implemented to them. Pinch means a decrease in the diffuser width. Four of the vaned diffusers have the same vane turning angle and a different number of vanes, and two have different vane turning angles. The flow solver used to solve the flow fields is Finflo, which is a Navier-Stokes solver. All the cases are modeled with the Chien's k – έ- turbulence model, and selected cases are modeled also with the k – ώ-SST turbulence model. All five vaneless diffusers and three vaned diffusers are investigated also experimentally. For each construction, the compressor operating map is measured according to relevant standards. In addition to this, the flow fields before and after the diffuser are measured with static and total pressure, flow angle and total temperature measurements. When comparing the computational results to the measured results, it is evident that the k – ώ-SST turbulence model predicts the flow fields better. The simulation results indicate that it is possible to improve the efficiency with the pinch, and according to the numerical results, the two best geometries are the ones with most pinch at the shroud. These geometries have approximately 4 percentage points higher efficiency than the unpinched vaneless diffusers. The hub pinch does not seem to have any major benefits. In general, the pinches make the flow fields before and after the diffuser more uniform. The pinch also seems to improve the impeller efficiency. This is down to two reasons. The major reason is that the pinch decreases the size of slow flow and possible backflow region located near the shroud after the impeller. Secondly, the pinches decrease the flow velocity in the tip clearance, leading to a smaller tip leakage flow and therefore slightly better impeller efficiency. Also some of the vaned diffusers improve the efficiency, the increment being 1...3 percentage points, when compared to the vaneless unpinched geometry. The measurement results confirm that the pinch is beneficial to the performance of the compressor. The flow fields are more uniform with the pinched cases, and the slow flow regions are smaller. The peak efficiency is approximately 2 percentage points and the design point efficiency approximately 4 percentage points higher with the pinched geometries than with the un- pinched geometry. According to the measurements, the two best geometries are the ones with the most pinch at the shroud, the case with the pinch only at the shroud being slightly better of the two. The vaned diffusers also have better efficiency than the vaneless unpinched geometries. However, the pinched cases have even better efficiencies. The vaned diffusers narrow the operating range considerably, whilst the pinch has no significant effect on the operating range.