Search

We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali’s O(n^5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Omega(1/(sqrt(n) log n)) and O(1/sqrt(n))---asymptotically tight up to an O(log n) factor---for the expansion of the associahedron graph K_n---the first o(1) expansion result for this graph. We show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k >= 4, and a treewidth result for the flip graph on n x n lattice triangulations.We show that the hardcore Glauber dynamics---a random walk on the independent sets of an input graph---mixes rapidly in graphs of bounded treewdith for all fixed values of the standard parameter lambda > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets and b-edge covers (for fixed b >= 1 and lambda > 0) in bounded-treewidth graphs, and for Markov chains on the b-matchings (for fixed b >= 1 and lambda > 0), the maximal independent sets, and the maximal b-matchings of a graph (for fixed b >= 1), in graphs of bounded carving width.To obtain these results, we introduce a decomposition framework for showing rapid Markov chain mixing. This framework is a purely combinatorial analogue that in some settings gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda.

3D multiple-view reconstruction is an important topic with applications in robotics, surveillance, augmented reality, and other fields. The ubiquity of reconstruction makes it a vital component in many systems, which need hardware and algorithms capable of processing the vast data found in reconstruction. In this dissertation, we first propose a method for performing a stage of reconstruction, triangulation, on the GPU that does not require second-order optimization and yields an order-of-magnitude speedup over a multi-core CPU processor. Next, we accelerate triangulation further on the GPU by discussing a method that leverages the path of a moving camera as a constraint and thus avoids doing non-linear optimization altogether. Subsequently, we shift to the problem of dense stereo, where we use GPU processing power to create more complete dense reconstructions while again leveraging scene constraints to keep runtime tractable. Finally, we devote a large portion of this dissertation to studying the use of multiple GPUs to accelerate the most expensive stage in reconstruction, bundle adjustment. The strategy is to partition the scene and optimize the subproblems in parallel. This approach minimizes communication across GPUs and removes the need for multi-GPU synchronization, which can be costly when there are many GPUs. We analyze multiple parallel, partitioned bundle adjustment strategies and their advantages and disadvantages. We develop an alternate method that parallelizes more efficiently and is scalable on large datasets with more GPUs. We compare the performance of the partitioned, parallel implementation against that of the original, full-problem implementation. We confirm our hypothesis that our approach can obtain large speedups with competitive accuracy for certain scenes but is less robust to ill-conditioned problems and the presence of local minima.

Molecular methods have revolutionised virtually every area of biology, and metazoan phylogenetics is no exception: molecular phylogenies, molecular clocks, comparative phylogenomics, and developmental genetics have generated a plethora of molecular data spanning numerous taxa and collectively transformed our understanding of the evolutionary history of animals, often corroborating but at times opposing results of more traditional approaches. Moreover, the diversity of methods and models within molecular phylogenetics has resulted in significant disagreement among molecular phylogenies as well as between these and earlier phylogenies. How should this broad and multifaceted problem be tackled? I argue that the answer lies in integrating evidence to infer the best evolutionary scenario. I begin with an overview of recent development in early metazoan phylogenetics, followed by a discussion of key conceptual issues in phylogenetics revolving around phylogenetic evidence, theory, methodology, and interrelations thereof. I then argue that the integration of different kinds of evidence (e.g. molecular, morphological, ecological) is necessary for arriving at the best evolutionary scenario (causal explanation) rather than merely the best-fitting cladogram (statistical explanation). Finally, I discuss the prospects of this view in stimulating interdisciplinary cross-talk in early metazoan research and beyond, and challenges that need to be overcome.

Minkowski timespace has the capability to overcome the limited accuracy of L2-norm based range-free localization methods. This paper proposes the concept of Minkowski triangulation uncertainty (MTU) in wireless sensor networks (WSNs) for localization of unknown target. To set up a localization framework, triangulation uncertainty parameter is defined using Lemma 3.1. A two-stage estimation algorithm is then presented: countLocalized and countAnchor. countLocalized computes the number of localized sensor nodes by leveraging the uncertainty strategy based upon indeterminate independent measurement. countAnchor designates the anchor nodes to triangulate the unknown target by formulating a convex hull model. The convex hull is the Minkowski sum of the actual and projected positions of the two vector node positions. The proposed MTU technique establishes that the number of triangulations formed by Minkowski method is inclusive of the triangulations formed by conventional L2-norm range of sensor nodes in a WSN. Measurement strategies such as angle, distance and positioning error are compared in the simulation. The said technique links Minkowski space to localization by ensuring efficiency in large target areas and number of nodes in manifolds. Results confirm that the MTU technique is better than the existing models by at least 12%, 50%, 5.5% and 24% in terms of localization ratio, localization error, neighbour anchor nodes and network connectivity, respectively.

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Moller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

Video-based facial expression recognition is a potential alternative for detecting the transitional processes of human emotion. In this paper, we present the landmark triangulation-induced altitude signatures to depict gradual changes in human emotion from face video frames. In our proposed approach, we consider the geometry-based triangulation technique which results from the triangles formed by important landmark points on face images. In this work, we measure three altitudes from all triangles and generate three different variations of altitude signature viz. AS1, AS2 and AS3 for the classification of six basic emotions viz. anger (AN), disgust (DI), fear (FE), happiness (HA), sadness (SA) and surprise (SU) in several ways. The performance capability of our proposed recognition system is tested on three benchmark face video datasets: Extended Cohn–Kanade (CK+), M&M Initiative (MMI), and Multimedia Understanding Group (MUG) through the application of Multilayer Perceptron (MLP) classifier and also validated by tenfold cross-validation method. Experimental results, 98.77%, 93.06%, and 98.75% on CK+, MMI, and MUG, respectively, are found very impressive. System efficacy is vindicated by showing the superiority of the proposed technique over the other existing techniques.

Machine learning and statistical methods can help model meteorological phenomena, especially in a context with many variables. However, it is not unusual that the measurement of those variables fails, generating data gaps and compromising data history analysis. The framework combines the predictions provided by three machine learning methods: decision trees, artificial neural networks and support vector machine, together with values calculated through five triangulation methods: arithmetic average, inverse distance weighted, optimized inverse distance weighted, optimized normal ratio and regional weight. Each machine learning algorithm generates eight regression models. One of the machine learning models makes predictions based only on the date. The remaining seven models make predictions based on one weather parameter (max. temperature, min. temperature, insolation, among others), in addition to the respective date. The triangulation methods use the climatic data from three neighboring cities to estimate the parameter of the target city. The generated dataset is, posteriorly, optimized by meta-learning algorithms. The results show that the additional information provided by the new machine learning models and the triangulation methods offered a significant increase in the accuracy of the imputed data. Moreover, the statistical analysis and coefficient of determination R² showed that the meta-learning model based on regression trees successfully combined the base-level outputs to generate outputs that best fill in the missing values of the time series studied in this paper.

Due to pathologies or age-related problems, in some disabled people, motor impairment is associated with cognitive and/or visual impairments. This combination of limitations unfortunately leads to an inability to move around independently. Indeed, their situation does not allow them to use a conventional electric wheelchair, for safety reasons, and for the moment there is no other technological solution providing safe movement capacity. This lack of access to an autonomous travel solution has the consequence of weakening the intellectual, personal, social, cultural and moral development, as well as the life expectancy, of the people concerned. In this context, our team is working on the development of an optoelectronic system that secures the displacement of electric wheelchairs. This is a large project that requires the development of several functionalities such as: the anti-collision of the wheelchair with its environment, the prevention of falls from the wheelchair on uneven levels, and the adaptation of the system mechanically and electronically to the majority of commercially available electric wheelchair models, among others. In this article, we introduce our solution for detecting dangerous height differences, also called “negative obstacles”, through the creation of a dedicated sensor. This sensor works by optical triangulation and can embed several laser beams in order to extend its detection zone. It has the particularity of being robust in direct sunlight and rain and has a sufficiently high measurement rate to be suitable for the displacement of electric wheelchairs. We develop an adapted algorithm, and point out compromises, in particular between the orientation of the laser beams and the maximal speed of the wheelchair.

Child–Computer Interaction (CCI) is a steadily growing field that focuses on children as a prominent and emergent user group. For more than twenty years, the Interaction Design for Children (IDC) community has developed, extended, and advanced research and design methods for children’s involvement in designing and evaluating interactive technologies. However, as the CCI field evolves, the need arises for an integrated understanding of interaction design methods currently applied. To that end, we analyzed 272 full papers across a selection of journals and conference venues from 2005 to 2020. Our review contributes to the literature on this topic by (1) examining a holistic child population, including developmentally diverse children and children from 0 to 18 years old, (2) illustrating the interplay of children’s and adults’ roles across different methods, and (3) identifying patterns of triangulation in the methods applied while taking recent ethical debates about children’s involvement in design into account. While we found that most studies were conducted in natural settings, we observed a preference for evaluating interactive artifacts at a single point in time. Method triangulation was applied in two-thirds of the papers, with a preference for qualitative methods. Researchers used triangulation predominantly with respect to mainstream methods that were not specifically developed for child participants, such as user observation combined with semi-structured interviews or activity logging. However, the CCI field employs a wide variety of creative design methods which engage children more actively in the design process by having them take on roles such as informant and design partner. In turn, we see that more passive children’s roles, e.g., user or tester, are more often linked to an expert mindset by the adult. Adults take on a wider spectrum of roles in the design process when addressing specific developmental groups, such as children with autism spectrum disorder. We conclude with a critical discussion about the constraints involved in conducting CCI research and discuss implications that can inform future methodological advances in the field and underlying challenges.

In the face of the "crisis of reproducibility" and the rise of "big data" with its associated issues, modeling needs to be practiced more critically and less automatically. Many modelers are discussing better modeling practices, but to address questions about the transparency, equity, and relevance of modeling, we also need the theoretical grounding of social science and the tools of critical theory. I have therefore synthesized recent work by modelers on better practices for modeling with social science literature (especially feminist science and technology studies) to offer a "modeler’s manifesto": a set of applied practices and framings for critical modeling approaches. Broadly, these practices involve 1) giving greater context to scientific modeling through extended methods sections, appendices, and companion articles, clarifying quantitative and qualitative reasoning and process; 2) greater collaboration in scientific modeling via triangulation with different data sources, gaining feedback from interdisciplinary teams, and viewing uncertainty as openness and invitation for dialogue; and 3) directly engaging with justice and ethics by watching for and mitigating unequal power dynamics in projects, facing the impacts and implications of the work throughout the process rather than only afterwards, and seeking opportunities to collaborate directly with people impacted by the modeling.

The detection of peaks (summits) as the upper parts of mountains and the delineation of their shape is commonly confirmed by inspections carried out by mountaineers. In this study the complex task of peak detection and shape delineation is solved by autometric methodological procedures, more precisely, by developing relatively simple but innovative image-processing and spatial-analysis techniques (e.g., developing inventive variables using an annular moving window) in remote sensing and GIS domains. The techniques have been integrated into automated morphometric methodological procedures. The concepts of peaks and their shapes (sharp, blunt, oblong, circular and conical) were parameterized based on topographic and morphologic criteria. A geomorphologically high quality DEM was used as a fundamental dataset. The results, detected peaks with delineated shapes, have been integratively enriched with numerous independent datasets (e.g., with triangulated spot heights) and information (e.g., etymological information), and mountaineering criteria have been implemented to improve the judgments. This holistic approach has proved the applicability of both highly standardized and universal parameters for the geomorphologically diverse Kamnik Alps case study area. Possible applications of this research are numerous, e.g., a comprehensive quality control of DEM or significantly improved models for the spatial planning proposes.

A single electro-optical (EO) sensor used in space debris observation provides angle-only information. However, space debris position can be derived using simultaneous optical measurements obtained from two EO sensors located at two separate observation sites, and this is commonly known as triangulation. In this paper, we propose a new triangulation algorithm to determine space debris position, and its analytical expression of Root-Mean-Square (RMS) position error is presented. The simulation of two-site observation is conducted to compare the RMS positioning error of the proposed triangulation algorithm with traditional triangulation algorithms. The results show that the maximum RMS position error of the proposed triangulation algorithm is not more than 200 m, the proposed triangulation algorithm has higher positioning accuracy than traditional triangulation algorithms, and the RMS position error obtained in the simulation is nearly consistent with the analytical expression of RMS position error. In addition, initial orbit determination (IOD) is carried out by using the triangulation positioning data, and the results show that the IOD accuracy of two-site observation is significantly higher than that of the single-site observation.

The availability of numerous online databases offers new and tremendous opportunities for social science research. Furthermore, databases based on news reports often allow scholars to investigate issues otherwise hard to tackle, such as, for example, the impact and consequences of drone strikes. Crucial to the campaign against terrorism, official data on drone strikes are classified, but news reports permit a certain degree of independent scrutiny. The quality of such research may be improved if scholars can rely on two (or more) databases independently reporting on the same issue (a solution akin to ‘data triangulation’). Given these conditions, such databases should be as reliable and valid as possible. This paper aimed to discuss the ‘validity and reliability’ of two such databases, as well as open up a debate on the evaluation of the quality, reliability and validity of research data on ‘problematic’ topics that have recently become more accessible thanks to online sources.

This study aims to analyze online based integrated social studies learning. This research method uses qualitative methods, namely research conducted by taking data sources using descriptive analysis. The location of this research is at SMP Negeri 35 Bandar Lampung. Data collection techniques using observation, interviews, documentation. This study uses data analysis with the Miles and Huberman model, namely through data reduction, data presentation, and drawing conclusions. The triangulation technique used is data source triangulation, technical triangulation, and time triangulation. The results of this study indicate that the implementation of online learning at SMP Negeri 35 Bandar Lampung. Online learning of teachers and students using the Whatsapp and Google Classroom applications has been carried out well.