Improving shortest paths in the Delaunay triangulation

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s; t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t in the Delaunay triangulation of P u{p} improves as much as possible. We study properties of the problem and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

Metaheuristic approaches for MWT and MWPT problems

It is known that the Minimum Weight Triangulation problem is NP-hard. Also the complexity of the Minimum Weight Pseudo-Triangulation problem is unknown, yet it is suspected to be also NP-hard. Therefore we focused on the development of approximate algorithms to find high quality triangulations and pseudo-triangulations of minimum weight. In this work we propose two metaheuristics to solve these problems: Ant Colony Optimization (ACO) and Simulated Annealing (SA). For the experimental study we have created a set of instances for MWT and MWPT problems, since no reference to benchmarks for these problems were found in the literature. Through experimental evaluation, we assess the applicability of the ACO and SA metaheuristics for MWT and MWPT problems. These results are compared with those obtained from the application of deterministic algorithms for the same problems (Delaunay Triangulation for MWT and a Greedy algorithm respectively for MWT and MWPT).

Refined facial disparity maps for automatic creation of 3D avatars

We propose a new method to automatically refine a facial disparity map obtained with standard cameras and under conventional illumination conditions by using a smart combination of traditional computer vision and 3D graphics techniques. Our system inputs two stereo images acquired with standard (calibrated) cameras and uses dense disparity estimation strategies to obtain a coarse initial disparity map, and SIFT to detect and match several feature points in the subjects face. We then use these points as anchors to modify the disparity in the facial area by building a Delaunay triangulation of their convex hull and interpolating their disparity values inside each triangle. We thus obtain a refined disparity map providing a much more accurate representation of the the subjects facial features. This refined facial disparity map may be easily transformed, through the camera calibration parameters, into a depth map to be used, also automatically, to improve the facial mesh of a 3D avatar to match the subjects real human features.

Reduction of truncation errors in planar, cylindrical and partial spherical near-field antenna measurements

A method to reduce truncation errors in near-field antenna measurements is presented. The method is based on the Gerchberg-Papoulis iterative algorithm used to extrapolate band-limited functions and it is able to extend the valid region of the calculated far-field pattern up to the whole forward hemisphere. The extension of the valid region is achieved by the iterative application of a transformation between two different domains. After each transformation, a filtering process that is based on known information at each domain is applied. The first domain is the spectral domain in which the plane wave spectrum (PWS) is reliable only within a known region. The second domain is the field distribution over the antenna under test (AUT) plane in which the desired field is assumed to be concentrated on the antenna aperture. The method can be applied to any scanning geometry, but in this paper, only the planar, cylindrical, and partial spherical near-field measurements are considered. Several simulation and measurement examples are presented to verify the effectiveness of the method.

Leftovers in seed dispersal: ecological implications of partial seed consumption for oak regeneration

1. Successful seed dispersal by animals is assumed to occur when undamaged seeds arrive at a favourable microsite. Most seed removal and dispersal studies consider only two possible seed fates, predation or escape intact. Whether partial consumption of seeds has ecological implications for natural regeneration is unclear. We studied partial consumption of seeds in a rodent-dispersed oak species. 2. Fifteen percent of dispersed acorns were found partially eaten in a field experiment. Most damage affected only the basal portion of the seeds, resulting in no embryo damage. Partially eaten acorns had no differences in dispersal distance compared to intact acorns but were recovered at farther distances than completely consumed acorns. 3. Partially eaten acorns were found under shrub cover unlike intact acorns that were mostly dispersed to open microhabitats. 4. Partially eaten acorns were not found buried proportionally more often than intact acorns, leading to desiccation and exposure to biotic agents (predators, bacteria and fungi). However, partial consumption caused more rapid germination, which enables the acorns to tolerate the negative effects of exposure. 5. Re-caching and shrub cover as microhabitat of destination promote partial seed consumption. Larger acorns escaped predation more often and had higher uneaten cotyledon mass. Satiation at seed level is the most plausible explanation for partial consumption. 6. Partial consumption caused no differences in root biomass when acorns experienced only small cotyledon loss. However, root biomass was lower when acorns experienced heavy loss of tissue but, surprisingly, they produced longer roots, which allow the seeds to gain access sooner to deeper resources. 7.Synthesis. Partial consumption of acorns is an important event in the oak regeneration process, both quantitatively and qualitatively. Most acorns were damaged non-lethally, without decreasing both dispersal distances and the probability of successful establishment. Faster germination and production of longer roots allow partially eaten seeds to tolerate better the exposure disadvantages caused by the removal of the pericarp and the non-buried deposition. Consequently, partially consumed seeds can contribute significantly to natural regeneration and must be considered in future seed dispersal studies.

A New Method to Reduce Truncation Errors in Partial Spherical Near-Field Measurements

A new and effective method for reduction of truncation errors in partial spherical near-field (SNF) measurements is proposed. The method is useful when measuring electrically large antennas, where the measurement time with the classical SNF technique is prohibitively long and an acquisition over the whole spherical surface is not practical. Therefore, to reduce the data acquisition time, partial sphere measurement is usually made, taking samples over a portion of the spherical surface in the direction of the main beam. But in this case, the radiation pattern is not known outside the measured angular sector as well as a truncation error is present in the calculated far-field pattern within this sector. The method is based on the Gerchberg-Papoulis algorithm used to extrapolate functions and it is able to extend the valid region of the calculated far-field pattern up to the whole forward hemisphere. To verify the effectiveness of the method, several examples are presented using both simulated and measured truncated near-field data.

Signal analysis and feature generation for pattern identification of partial discharges in high-voltage equipment

This paper proposes a method for the identification of different partial discharges (PDs) sources through the analysis of a collection of PD signals acquired with a PD measurement system. This method, robust and sensitive enough to cope with noisy data and external interferences, combines the characterization of each signal from the collection, with a clustering procedure, the CLARA algorithm. Several features are proposed for the characterization of the signals, being the wavelet variances, the frequency estimated with the Prony method, and the energy, the most relevant for the performance of the clustering procedure. The result of the unsupervised classification is a set of clusters each containing those signals which are more similar to each other than to those in other clusters. The analysis of the classification results permits both the identification of different PD sources and the discrimination between original PD signals, reflections, noise and external interferences. The methods and graphical tools detailed in this paper have been coded and published as a contributed package of the R environment under a GNU/GPL license.

Program debugging and validation using semantic approximations and partial specifications

The technique of Abstract Interpretation [11] has allowed the development of sophisticated program analyses which are provably correct and practical. The semantic approximations produced by such analyses have been traditionally applied to optimization during program compilation. However, recently, novel and promising applications of semantic approximations have been proposed in the more general context of program validation and debugging [3,9,7].

Partial order and contextual net semantics for atomic and locally atomic CC programs

We present two concurrent semantics (i.e. semantics where concurrency is explicitely represented) for CC programs with atomic tells. One is based on simple partial orders of computation steps, while the other one is based on contextual nets and it is an extensión of a previous one for eventual CC programs. Both such semantics allow us to derive concurrency, dependency, and nondeterminism information for the considered languages. We prove some properties about the relation between the two semantics, and also about the relation between them and the operational semantics. Moreover, we discuss how to use the contextual net semantics in the context of CLP programs. More precisely, by interpreting concurrency as possible parallelism, our semantics can be useful for a safe parallelization of some CLP computation steps. Dually, the dependency information may also be interpreted as necessary sequentialization, thus possibly exploiting it for the task of scheduling CC programs. Moreover, our semantics is also suitable for CC programs with a new kind of atomic tell (called locally atomic tell), which checks for consistency only the constraints it depends on. Such a tell achieves a reasonable trade-off between efficiency and atomicity, since the checked constraints can be stored in a local memory and are thus easily accessible even in a distributed implementation.

Using global analysis, partial specifications, and an extensible assertion language for program validation and debugging

We discuss a framework for the application of abstract interpretation as an aid during program development, rather than in the more traditional application of program optimization. Program validation and detection of errors is first performed statically by comparing (partial) specifications written in terms of assertions against information obtained from (global) static analysis of the program. The results of this process are expressed in the user assertion language. Assertions (or parts of assertions) which cannot be checked statically are translated into run-time tests. The framework allows the use of assertions to be optional. It also allows using very general properties in assertions, beyond the predefined set understandable by the static analyzer and including properties defined by user programs. We also report briefly on an implementation of the framework. The resulting tool generates and checks assertions for Prolog, CLP(R), and CHIP/CLP(fd) programs, and integrates compile-time and run-time checking in a uniform way. The tool allows using properties such as types, modes, non-failure, determinacy, and computational cost, and can treat modules separately, performing incremental analysis.

An integration of partial evaluation in a generic abstract interpretation framework

Information generated by abstract interpreters has long been used to perform program specialization. Additionally, if the abstract interpreter generates a multivariant analysis, it is also possible to perform múltiple specialization. Information about valúes of variables is propagated by simulating program execution and performing fixpoint computations for recursive calis. In contrast, traditional partial evaluators (mainly) use unfolding for both propagating valúes of variables and transforming the program. It is known that abstract interpretation is a better technique for propagating success valúes than unfolding. However, the program transformations induced by unfolding may lead to important optimizations which are not directly achievable in the existing frameworks for múltiple specialization based on abstract interpretation. The aim of this work is to devise a specialization framework which integrates the better information propagation of abstract interpretation with the powerful program transformations performed by partial evaluation, and which can be implemented via small modifications to existing generic abstract interpreters. With this aim, we will relate top-down abstract interpretation with traditional concepts in partial evaluation and sketch how the sophisticated techniques developed for controlling partial evaluation can be adapted to the proposed specialization framework. We conclude that there can be both practical and conceptual advantages in the proposed integration of partial evaluation and abstract interpretation.

Towards Integrating Partial Evaluation in a Specialization Framework based on Generic Abstract Interpretation

Abstract is not available

Using global analysis, partial specifications, and an extensible assertion language for program validation and debugging

We present a framework for the application of abstract interpretation as an aid during program development, rather than in the more traditional application of program optimization. Program validation and detection of errors is first performed statically by comparing (partial) specifications written in terms of assertions against information obtained from static analysis of the program. The results of this process are expressed in the user assertion language. Assertions (or parts of assertions) which cannot be verified statically are translated into run-time tests. The framework allows the use of assertions to be optional. It also allows using very general properties in assertions, beyond the predefined set understandable by the static analyzer and including properties defined by means of user programs. We also report briefly on an implementation of the framework. The resulting tool generates and checks assertions for Prolog, CLP(R), and CHIP/CLP(fd) programs, and integrates compile-time and run-time checking in a uniform way. The tool allows using properties such as types, modes, non-failure, determinacy, and computational cost, and can treat modules separately, performing incremental analysis. In practice, this modularity allows detecting statically bugs in user programs even if they do not contain any assertions.

Approximations on minimum weight pseudo-triangulation problem using ant colony optimization

In this work, we consider the Minimum Weight Pseudo-Triangulation (MWPT) problem of a given set of n points in the plane. Globally optimal pseudo-triangulations with respect to the weight, as optimization criteria, are difficult to be found by deterministic methods, since no polynomial algorithm is known. We show how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality pseudo-triangulations of minimum weight. We present the experimental and statistical study based on our own set of instances since no reference to benchmarks for these problems were found in the literature. Throughout the experimental evaluation, we appraise the ACO metaheuristic performance for MWPT problem.

Estudio del impacto del usuario final en los procesos de desarrollo de sistemas de información

Durante décadas y aun en la actualidad muchas organizaciones, a nivel mundial, continúan afrontando pérdidas significativas debido a fracasos parciales y totales respecto a sus inversiones en sistemas de información (SI), planteando serios retos a los niveles gerenciales y los profesionales de SI. Estadísticas alarmantes y décadas de experiencia en la praxis en el área de SI en diversas organizaciones llevan al autor a poner el énfasis en los usuarios finales internos (UF) que son designados como representantes (UFR) de sus pares en los proyectos de desarrollo de SI (PDSI) por considerarlos como factores influyentes de manera significativa en el problema. Particularmente, con enfoque en ciertos factores de los UFR críticos para el éxito de los PDSI, con dimensiones analizadas de forma aislada o incompleta en otros estudios empíricos, a la fecha. No se encontraron estudios en Latinoamérica ni en otras latitudes que abordasen el fenómeno del éxito/fracaso de los SI desde el punto de vista adoptado en esta tesis. Por ello, esta investigación empírica ha evaluado en qué grado estos factores pudiesen influenciar los resultados durante el desarrollo e implementación de SI y su posible impacto en la satisfacción de los UF, siendo esta última aceptada por variados autores como la principal medida del éxito de los SI. Este estudio fue realizado en América Latina en las cuatro grandes empresas industriales que integran verticalmente el sector aluminio de Venezuela, sometidas a un macro PDSI para instalar el paquete, de tipo ERP, SAP/R3. Experimentados profesionales fueron encuestados o entrevistados, tales como altos ejecutivos, desarrolladores, líderes de proyecto y líderes de los UF. Un enfoque metodológico de triangulación permitió combinar un análisis cuantitativo con un análisis cualitativo interpretativo del tipo hermenéutico/dialéctico, hallándose resultados convergentes y complementarios. Un análisis estadístico, utilizando Partial Least Squares (PLS), seguido de un análisis hermenéutico/dialéctico. Los resultados confirmaron un hecho importante: en los casos problemáticos, paradójicamente, los orígenes de las razones de rechazo de esos SI argumentadas por los UF, en alto grado, apuntaron a los UFR o a ellos mismos. Los resultados también confirmaron la prevalencia de factores de orden cognitivo, conductual y político en estas organizaciones sobre los tecnológicos, al igual que el alto riesgo de dar por sentado la presencia y calidad de los factores requeridos de los UFR y de los otros factores estudiados. La validación estadística del modelo propuesto reveló al constructo conocimientos de los UFR como la principal variable latente, con los variables indicadoras que componen este constructo ejerciendo la mayor influencia sobre la calidad y el éxito de los SI. Un hallazgo contrario al de otros estudios, mostró que los conocimientos sobre las tecnologías de la información (TI) fueron los menos relevantes. Los SI de nómina y de administración de los RRHH fueron los más problemáticos, como suele ser el caso, por su complejidad en organizaciones grandes. Las conclusiones principales confirman el decisivo rol de los UF para el éxito de los PDSI y su relación con la creciente problemática planteada, la cual amerita más investigación y de las organizaciones una mayor atención y preparación. Descuidar los factores humanos y sociales así como una efectiva planificación y gestión de los mismos en preparación para estos proyectos origina serios riesgos. No obstante las limitaciones de este trabajo, la problemática analizada suele influir en los PDSI en diversas organizaciones, indistintamente de su tamaño o tipo de SI, estimándose, por tanto, que los resultados, conclusiones y recomendaciones de esta investigación tienen un alto grado de generalización. Una relación de indicadores claves es suministrada con fines preventivos. Finalmente, los factores evaluados pueden usarse para ampliar el modelo reconocido de DeLone y McLean (2003), conectándolos como variables latentes de sus variables independientes calidad de la información y calidad del SI. ABSTRACT For decades, many organizations worldwide have been enduring heavy losses due to partial and total failures regarding their investments in information systems (IS), posing serious challenges to all management levels and IS practitioners. Alarming statistics in this regard and decades of practice in the IS area lead the author to place an emphasis on the end users (EU) who are appointed in representation of their peers (EUR) to IS development projects (ISDP), considering them as highly influential factors on the problem. Especially, focusing on certain EUR success factors, and their dimensions, deemed critical to any IS development and implementation, omitted or not thoroughly analyzed neither in the theory nor in the empirical research on the subject, so far. No studies were found in Latin America or elsewhere addressing the phenomenon of IS success/failure from the perspective presented herein. Hence, this empirical research has assessed to what degree such factors can influence the outcomes of an ISDP and their feasible impact on the EU´s satisfaction, being the latter accepted by several authors as the main measure of IS success. This study was performed in Latin America embracing four major industrial enterprises, which vertically integrate the aluminum sector of Venezuela, subjected to a macro ISDP to install the ERP-type package SAP/R3. The field work included surveying and interviewing experienced professionals such as IS executives, IS developers, IS project leaders and end-user project leaders. A triangulation methodological approach allowed combining quantitative and interpretive analyses, obtaining convergent and complementing results. A statistical analysis, using Partial Least Squares (PLS), was carried out followed by a hermeneutical/dialectical analysis. Results confirmed a major finding: in problematic cases, paradoxically, the origins of IS rejection reasons argued by the EU, at a high degree, were usually traceable to the EUR and themselves. The results also confirmed the prevalence of cognitive, behavioral and political factors in these organizations as well as the high risk of taking for granted the presence and quality of those factors demanded from the EUR. The statistical validation of the proposed model revealed the construct EUR knowledge as the main latent variable, with its items exerting a major influence on IS quality and success. Another finding, in contradiction with that of other studies, proved knowledge of information technology (IT) aspects to be irrelevant. The payroll and the human resources administration IS were the most problematic, as is usually the case in large companies. The main conclusions confirm the EU´s decisive role for IS success and their relationship with the problem, which continues, demanding more research and, from organizations, more attention and preparation. Neglecting human and social factors in organizations as well as their effective planning and management in preparation for ISDP poses serious risks. Despite the limitations of this work, the analyzed problem tends to influence ISDP in a wide range of organizations; regardless of their size or type of IS, thus showing a high degree of generalization. Therefore it is believed that the results, conclusions and suggestions of this research have a high degree of generalization. A detailed checklist comprising key measures is provided for preventive actions. Finally, the factors evaluated can be used to expand the well-known model of DeLone & McLean (2003), by connecting them as latent variables of its independent variables information quality and IS quality.