Generalized Higher-Order Voronoi Diagrams on Polyhedral Surfaces

We present an algorithm for computing exact shortest paths, and consequently distances, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex polyhedral surface in which polygonal chain or polygon obstacles are allowed. We also present algorithms for computing discrete Voronoi diagrams of a set of generalized sites (points, segments, polygonal chains or polygons) on a polyhedral surface with obstacles. To obtain the discrete Voronoi diagrams our algorithms, exploiting hardware graphics capabilities, compute shortest path distances defined by the sites

A compositional data analysis package for R providing multiple approaches

”compositions” is a new R-package for the analysis of compositional and positive data. It contains four classes corresponding to the four different types of compositional and positive geometry (including the Aitchison geometry). It provides means for computation, plotting and high-level multivariate statistical analysis in all four geometries. These geometries are treated in an fully analogous way, based on the principle of working in coordinates, and the object-oriented programming paradigm of R. In this way, called functions automatically select the most appropriate type of analysis as a function of the geometry. The graphical capabilities include ternary diagrams and tetrahedrons, various compositional plots (boxplots, barplots, piecharts) and extensive graphical tools for principal components. Afterwards, ortion and proportion lines, straight lines and ellipses in all geometries can be added to plots. The package is accompanied by a hands-on-introduction, documentation for every function, demos of the graphical capabilities and plenty of usage examples. It allows direct and parallel computation in all four vector spaces and provides the beginner with a copy-and-paste style of data analysis, while letting advanced users keep the functionality and customizability they demand of R, as well as all necessary tools to add own analysis routines. A complete example is included in the appendix

Compositional Data Analysis with R

R from http://www.r-project.org/ is ‘GNU S’ – a language and environment for statistical computing and graphics. The environment in which many classical and modern statistical techniques have been implemented, but many are supplied as packages. There are 8 standard packages and many more are available through the cran family of Internet sites http://cran.r-project.org . We started to develop a library of functions in R to support the analysis of mixtures and our goal is a MixeR package for compositional data analysis that provides support for operations on compositions: perturbation and power multiplication, subcomposition with or without residuals, centering of the data, computing Aitchison’s, Euclidean, Bhattacharyya distances, compositional Kullback-Leibler divergence etc. graphical presentation of compositions in ternary diagrams and tetrahedrons with additional features: barycenter, geometric mean of the data set, the percentiles lines, marking and coloring of subsets of the data set, theirs geometric means, notation of individual data in the set . . . dealing with zeros and missing values in compositional data sets with R procedures for simple and multiplicative replacement strategy, the time series analysis of compositional data. We’ll present the current status of MixeR development and illustrate its use on selected data sets

When zero doesn't mean it and other geomathematical mischief

There is almost not a case in exploration geology, where the studied data doesn’t includes below detection limits and/or zero values, and since most of the geological data responds to lognormal distributions, these “zero data” represent a mathematical challenge for the interpretation. We need to start by recognizing that there are zero values in geology. For example the amount of quartz in a foyaite (nepheline syenite) is zero, since quartz cannot co-exists with nepheline. Another common essential zero is a North azimuth, however we can always change that zero for the value of 360°. These are known as “Essential zeros”, but what can we do with “Rounded zeros” that are the result of below the detection limit of the equipment? Amalgamation, e.g. adding Na2O and K2O, as total alkalis is a solution, but sometimes we need to differentiate between a sodic and a potassic alteration. Pre-classification into groups requires a good knowledge of the distribution of the data and the geochemical characteristics of the groups which is not always available. Considering the zero values equal to the limit of detection of the used equipment will generate spurious distributions, especially in ternary diagrams. Same situation will occur if we replace the zero values by a small amount using non-parametric or parametric techniques (imputation). The method that we are proposing takes into consideration the well known relationships between some elements. For example, in copper porphyry deposits, there is always a good direct correlation between the copper values and the molybdenum ones, but while copper will always be above the limit of detection, many of the molybdenum values will be “rounded zeros”. So, we will take the lower quartile of the real molybdenum values and establish a regression equation with copper, and then we will estimate the “rounded” zero values of molybdenum by their corresponding copper values. The method could be applied to any type of data, provided we establish first their correlation dependency. One of the main advantages of this method is that we do not obtain a fixed value for the “rounded zeros”, but one that depends on the value of the other variable. Key words: compositional data analysis, treatment of zeros, essential zeros, rounded zeros, correlation dependency

Mixing compositions and other scales

Theory of compositional data analysis is often focused on the composition only. However in practical applications we often treat a composition together with covariables with some other scale. This contribution systematically gathers and develop statistical tools for this situation. For instance, for the graphical display of the dependence of a composition with a categorical variable, a colored set of ternary diagrams might be a good idea for a first look at the data, but it will fast hide important aspects if the composition has many parts, or it takes extreme values. On the other hand colored scatterplots of ilr components could not be very instructive for the analyst, if the conventional, black-box ilr is used. Thinking on terms of the Euclidean structure of the simplex, we suggest to set up appropriate projections, which on one side show the compositional geometry and on the other side are still comprehensible by a non-expert analyst, readable for all locations and scales of the data. This is e.g. done by defining special balance displays with carefully- selected axes. Following this idea, we need to systematically ask how to display, explore, describe, and test the relation to complementary or explanatory data of categorical, real, ratio or again compositional scales. This contribution shows that it is sufficient to use some basic concepts and very few advanced tools from multivariate statistics (principal covariances, multivariate linear models, trellis or parallel plots, etc.) to build appropriate procedures for all these combinations of scales. This has some fundamental implications in their software implementation, and how might they be taught to analysts not already experts in multivariate analysis

Computing Distance Functions from Generalized Sources on Weighted Polyhedral Surfaces

We present algorithms for computing approximate distance functions and shortest paths from a generalized source (point, segment, polygonal chain or polygonal region) on a weighted non-convex polyhedral surface in which obstacles (represented by polygonal chains or polygons) are allowed. We also describe an algorithm for discretizing, by using graphics hardware capabilities, distance functions. Finally, we present algorithms for computing discrete k-order Voronoi diagrams

Metodologia de disseny conceptual d'estacions depuradores d'aigües residuals que combina el procés de decisió jeràrquic amb l'anàlisi de decisions multicriteri

La present tesi proposa una metodologia de disseny conceptual d'estacions depuradores d'aigües residuals (EDAR) mitjançant la combinació del procés de decisió jeràrquic i l'anàlisi de decisions multicriteri. El document s'inicia amb una breu introducció als principals camps abordats pel treball: el disseny dels processos químics en general, el disseny de les estacions depuradores d'aigües residuals en particular, i l'anàlisi de decisions multicriteri aplicada a la gestió ambiental. Seguidament, es fixen els objectius del treball i es descriuen tant la metodologia com el material de suport informàtic utilitzats. Per validar i contrastar la metodologia de disseny presentada, es desenvolupa un cas d'estudi on es porta a terme el disseny conceptual d'una EDAR que presenta els mateixos requeriments que l'EDAR que opera actualment al municipi de Granollers. Inicialment es presenta la informació de partida i tot seguit es defineixen els objectius de disseny, així com el conjunt de criteris que s'utilitzaran per avaluar en quina mesura es compleixen aquests objectius. Els objectius de disseny són de diferents tipus: ambientals, tècnics, socials i econòmics, i el conjunt de criteris utilitzats, concretament 33, també es classifica segons aquestes quatre categories. Cadascun dels criteris presenta un determinat pes d'importància relativa en la presa de decisions. Finalment, es desenvolupa tot el procés de decisió fins a obtenir el disseny complet de l'EDAR. El procés de decisió s'ha dividit en dues parts diferenciades però que alhora s'entrellacen: la línia d'aigua i la línia de fang. El procés de decisió presenta un total de divuit qüestions amb un màxim de quatre alternatives per pregunta (dotze qüestions corresponen a la línia d'aigua, i sis a la línia de fangs). Per solucionar cadascuna d'aquestes qüestions, s'avaluen les alternatives proposades respecte a un conjunt de criteris triats de la llista inicial. Aplicant el procés de decisió multicriteri anomenat SMART (simple multiattribute rating technique), es combinen els resultats de les alternatives respecte a cada criteri, tenint en compte la importància de cada criteri per obtenir un sol valor per alternativa. Per quantificar els criteris referents a l'operació del procés i les de tipus econòmic s'han utilitzat els programes GPS-X i CapdetWorks respectivament. Pel que fa als criteris no quantificats mitjançant aquests programes, s'han resolt de manera qualitativa i mitjançant manuals de disseny i també tenint en compte l'opinió d'experts en aquest camp. L'alternativa que obté un pes més elevat és la recomanada per al procés de decisió. El cas d'estudi finalitza un cop s'obté el disseny complet de l'EDAR. Per integrar tots aquests elements que hem esmentat i donar suport al desenvolupament del procés de decisió s'ha utilitzat el programa DRAMA (Design Rationale Management). A continuació, es fa una anàlisi comparativa entre l'EDAR que hi ha actualment al municipi de Granollers i l'EDAR resultat del cas d'estudi. Es descriu el diagrama de flux que conforma l'EDAR de Granollers i el diagrama de flux de l'EDAR resultat de l'estudi, se'n fa una anàlisi comparativa justificant cadascuna de les decisions preses en el cas d'estudi i, finalment, es fa una discussió de resultats on es reflecteixen els avantatges associats d'aplicar la metodologia de disseny conceptual proposada. Finalment, es presenten les conclusions de la tesi. Els principals resultats de la tesi es van publicar el 2002 a la revista internacional Industrial and Engineering Chemistry Research (N. Vidal, R. Bañares-Alcántara, I. Rodríguez-Roda i M. Poch: "Design of wastewater treatment plants using a conceptual design methodology", Industrial and Engineering Chemistry Research, 41 (20), pàg. 4993-5005) i la continuació de la línia de recerca al Laboratori d'Enginyeria Química i Ambiental de la UdG ha comportat la presentació del treball de recerca de Xavi Flores "Procés de decisió jeràrquic combinat amb anàlisi multicriteri per al suport al disseny conceptual de sistemes de fangs actius d'una estació depuradora d'aigües residuals" i la presentació dels resultats parcials al congrés internacional de la 9th IWA Conference on Design, Operation and Economics of Large Wastewater Treatment, que va tenir lloc el setembre passat a Praga ("Combining hierarchical decision process with multi-criteria analysis for conceptual design of WWTP", X. Flores, N. Vidal, A. Bonmatí, J. B. Copp i I. Rodríguez-Roda).

Entorno virtual para el aprendizaje y la evaluación automática en bases de datos

La enseñanza y evaluación automática a través de un sistema Computer Based Assessment (CBA) requiere de software especializado que se adapte a la tipología de actividades a tratar y evaluar. En esta tesis se ha desarrollado un entorno CBA que facilita el aprendizaje y evaluación de los principales temas de una asignatura de bases de datos. Para ello se han analizado las herramientas existentes en cada uno de estos temas (Diagramas Entidad/Relación, diagramas de clases, esquemas de bases de datos relacionales, normalización, consultas en álgebra relacional y lenguaje SQL) y para cada uno de ellos se ha analizado, diseñado e implementado un módulo de corrección y evaluación automática que aporta mejoras respecto a los existentes. Estos módulos se han integrado en un mismo entorno al que hemos llamado ACME-DB.

Visibility and proximity on triangulated surfaces

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem: punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmes de geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada per calcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Com a aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntes sobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos.