Search results for "Algorithm"
showing 10 items of 4887 documents
Expansive Voronoi Tree: A Motion Planner for Assembly Sequence Planning
2021
One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find an appropriate disassembly path for each assembled part. Complex real-world scenes are characterized by a large installation space. There each part has many different possible disassembly paths that differ in length and clearance. However, due to tight packing in the installation space, these paths can contain narrow passages. Therefore a motion planner is needed that is able to globally search for a reasonable path and to locally overcome narrow passages. Moreover, since motion planning requests are executed in the ASP context over and over again for many parts, both for those that can b…
Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
2020
In 1996, Bodlaender showed the celebrated result that an optimal tree decomposition of a graph of bounded treewidth can be found in linear time. The algorithm is based on an algorithm of Bodlaender and Kloks that computes an optimal tree decomposition given a non-optimal tree decomposition of bounded width. Both algorithms, in particular the second, are hardly accessible. We present the second algorithm in a much simpler way in this paper and refer to an extended version for the first. In our description of the second algorithm, we start by explaining how all tree decompositions of subtrees defined by the nodes of the given tree decomposition can be enumerated. We group tree decompositions …
Visualization of Large Terrain Using Non-restricted Quadtree Triangulations
2004
This paper presents a set of new techniques oriented towards the real-time visualization of large terrains. These techniques are mainly focused on semi-regular triangulations of non-restricted quadtree terrain representations. Despite the fact that the paper shows that triangulations based on non-restricted quadtrees are as simple and efficient as those based on restricted quadtrees, the new triangulations avoid discontinuity problems among the boundaries of different patches without the need for tree balancing and extra triangles addition. Another important feature of the proposed triangulation is that it incorporates an efficient method for building triangle strips and triangle fans for t…
Optimization of Low-Cost Monitoring Systems for On-Site Earthquake Early-Warning of Critical Infrastructures
2020
In the last years, monitoring systems based on low-cost and miniaturized sensors (MEMS) revealed as a very successful compromise between the availability of data and their quality. Also applications in the field of seismic and structural monitoring have been constantly increasing in term of number and variety of functions. Among these applications, the implementation of systems for earthquake early warning is a cutting-edge topic, mainly for its relevance for the society as millions of peoples in various regions of the world are exposed to high seismic hazard. This paper introduces the optimization of an already established seismic (and structural) monitoring system, that would make it suit…
Quasispecies dynamics and molecular evolution of human norovirus capsid P region during chronic infection.
2009
In this novel study, we have for the first time identified evolutionarily conserved capsid residues in an individual chronically infected with norovirus (GGII.3). From 2000 to 2003, a total of 147 P1-1 and P2 capsid sequences were sequenced and investigated for evolutionarily conserved and functionally important residues by the evolutionary trace (ET) algorithm. The ET algorithm revealed more absolutely conserved residues (ACR) in the P1-1 domain (47/53, 88 %) as compared with the P2 domain (86/133, 64 %). The capsid P1-1 and P2 domains evolved in time-dependent manner, with a distinct break point observed between autumn/winter of year 2000 (isolates P1, P3 and P5) and spring to autumn of y…
Algorithms for Pallet Building and Truck Loading in an Interdepot Transportation Problem
2016
This paper deals with the problem of a logistics company that has to serve its customers by first putting the products on pallets and then loading the pallets into trucks. Besides the standard geometric constraints of products not overlapping each other and not exceeding the dimensions of pallets and trucks, in this real problem, there are many other constraints, related to the total weight of the load, the maximum weight supported by each axle, and the distribution of the load inside the truck. Although the problem can be decomposed into two phases, pallet loading and truck loading, we have taken a combined approach, building and placing pallets at the same time. For each position in the t…
A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots
2016
International audience; In the single truck and trailer routing problem with satellite depots (STTRPSD), a truck with a detachable trailer based at a main depot must serve the demand of a set of customers accessible only by truck. Therefore, before serving the customers, it is necessary to detach the trailer in an appropriate parking place (called either a satellite depot or a trailer point) and transfer goods between the truck and the trailer. This problem has applications in milk collection for farms that cannot be reached using large vehicles. In this work we present an integer programming formulation of the STTRPSD. This formulation is tightened with several families of valid inequaliti…
From COVID-19 to future electrification: Assessing traffic impacts on air quality by a machine-learning model
2021
The large fluctuations in traffic during the COVID-19 pandemic provide an unparalleled opportunity to assess vehicle emission control efficacy. Here we develop a random-forest regression model, based on the large volume of real-time observational data during COVID-19, to predict surface-level NO(2), O(3), and fine particle concentration in the Los Angeles megacity. Our model exhibits high fidelity in reproducing pollutant concentrations in the Los Angeles Basin and identifies major factors controlling each species. During the strictest lockdown period, traffic reduction led to decreases in NO(2) and particulate matter with aerodynamic diameters <2.5 μm by –30.1% and –17.5%, respectively, bu…
$O(n^2 log n)$ Time On-line Construction of Two-Dimensional Suffix Trees
2007
The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of A [11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11], [18]. Motivated by applications in Image Compression [22], Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an O(n2 log2 n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen’s on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an O(logn) factor improvement in the time comple…
Evaluation of an Algorithm for Retrospective Hypoglycemia Detection Using Professional Continuous Glucose Monitoring Data.
2014
Background: People with type 1 diabetes (T1D) are unable to produce insulin and thus rely on exogenous supply to lower their blood glucose. Studies have shown that intensive insulin therapy reduces the risk of late-diabetic complications by lowering average blood glucose. However, the therapy leads to increased incidence of hypoglycemia. Although inaccurate, professional continuous glucose monitoring (PCGM) can be used to identify hypoglycemic events, which can be useful for adjusting glucose-regulating factors. New pattern classification approaches based on identifying hypoglycemic events through retrospective analysis of PCGM data have shown promising results. The aim of this study was to…