China
Africa
Explore chapters and articles related to this topic
Spatial Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
The point of searching with a KD tree is analogous to searching in other types of trees. For searching a query point xq=(xq1,xiq,…,xqd) in a KD tree, we start the comparison of xq1 with the first coordinate of root, followed by the comparison of xq2 with the second coordinate of selected child of root and so on. Once the search process reaches the leaf, we decide whether the point exists in the tree or not based on an exact match or failure. The complexity of search process is O(log n) for a balanced KD tree consisting of n nodes.
Data Gathering Algorithms for Wireless Sensor Networks
Published in Shafiullah Khan, Al-Sakib Khan Pathan, Nabil Ali Alrajeh, Wireless Sensor Networks, 2016
If the algorithm runs until all the nodes in the network are covered, it returns the following five data structures/variables that are used to compute the delay per round associated with the EMLN-DG tree: Intermediate-Nodes-List, Leaf-Nodes-List, Nodes-All-Levels, Height-DG-Tree, and rootNode. The time complexity of the algorithm is O(|V| *(|V|+|E|)), as it takes O(|V|+|E|) time per iteration and at most there could be O(|V|) intermediate nodes in the tree. For each of the iterations, we have to recompute the number of uncovered neighbors for every node in the network. There are |V| nodes in the network, and we have to process each of the |E| edges twice, once for each vertex on which the edge is incident.
Look-Up Table-Based Binary Coded Decimal Adder
Published in Hafiz Md. Hasan Babu, VLSI Circuits and Embedded Systems, 2023
The BCD addition method can be represented as a tree-structure as it is parallel which is shown in Fig. 16.3. There are basically two operational levels of the tree. Starting from the inputs, in Level 1, the bit-wise addition is performed and the intermediary resultants are obtained. Then, in Level 2, the addition and correction are performed providing the correct BCD output. Hence, the time complexity of the algorithm is logarithmic according to the operational depth of the tree. Property 16.1 is given to prove the time complexity of the method.
Recognition and robot grasping of disordered workpieces with 3D laser line profile sensor
Published in Systems Science & Control Engineering, 2023
Bin Ye, Zheng Wu, Sikui He, Huijun Li
For the point cloud fine registration, it is completed by using the iterative closest point (ICP) algorithm with bidirectional k-d tree search acceleration. In the ICP registration algorithm, it is necessary to find the nearest target point for each point in the source point cloud. If we traverse the points in the target point cloud and calculate the distance between the pairs of points, the efficiency is greatly reduced (Sun et al., 2010). K-d tree is a tree data structure that stores instance points in k-dimensional space for fast retrieval of them, so we construct a bidirectional k-dimensional tree for the point cloud to achieve a fast nearest neighbour search and at the same time, remove the points with Euclidean distance greater than a threshold value and save the points with high alignment accuracy to improve the alignment efficiency. The advantage of the bidirectional k-dimension tree is that the execution time of the algorithm is greatly reduced, and it avoids the wrong search of the nearest neighbour points. For the stacked workpieces, the point cloud usually only contains their visible surface. Thus, the point cloud fine registration based on the bidirectional k-d tree search will increase the registration accuracy.
Machine Learning Surrogates of a Fuel Matrix Degradation Process Model for Performance Assessment of a Nuclear Waste Repository
Published in Nuclear Technology, 2023
Bert J. Debusschere, D. Thomas Seidl, Timothy M. Berg, Kyung Won Chang, Rosemary C. Leone, Laura P. Swiler, Paul E. Mariner
The Fortran implementation of kNNr was built on the open-source module KDTREE 2 (Ref. 19), which is a Fortran tabulation library built for speed and with a limited but adequate set of kNNr features. Developed at the University of California, San Diego, Institute for Nonlinear Science, KDTREE 2 is a Fortran95 module written with “considerable care … in the implementation of the search methods, resulting in substantially higher computational efficiency.” Specifically, the k-d data structure and search algorithms are the generalization of classical binary search trees to higher dimensional spaces, so that one may locate near neighbors to an example vector in O(log N) time instead of the brute-force O(N) time, with N being the size of the data base.19