Dynamic algorithms in computational geometry

Article Abstract:

Dynamic algorithms involve updating the solution of a problem when the problem instance is modified. This computational framework provides considerable savings if the new solution does not have to be developed from scratch, especially when the problem is large-scale. Data structures in computational geometry include asymptotic notation, balanced trees and fractional cascading. Techniques for constructing dynamic data structures from static ones include global rebuilding, in which the entire data structure is reconstructed; the equal block method, which partitions S into f(n) subsets of roughly equal size; and the logarithmic method, which partitions S into O(log n) sets of sizes given by the powers of 2 in the binary representation of n. Also discussed is range searching, intersections, point location, convex hull and other problems.

Algorithms, Algorithm, Data structures, Scientific Research

---

Parallel techniques for computational geometry

Article Abstract:

Parallel computing provides greater problem-solving speed than sequential processing in the area of computational geometry, which makes the study of the ways in which this speedup is achieved crucial. Models of parallel computation for which parallel geometric algorithms have been designed include the PRAM model, where the processors operate synchronously, and hybrid models, which consist of more than one type of machine. Basic subproblems occur ubiquitously in the design of parallel geometric algorithms regardless of the model used. Subroutines for solving these problems include sorting and merging, parallel prefix, list ranking and tree contraction. PRAM techniques include inherently sequential geometric problems, fast and efficient methods, and the divide and conquer technique. Other PRAM techniques are discussed.

Problem solving, Computer science, Parallel processing, Divide and Conquer

---

Similar abstracts:

• Abstracts: Disk system architectures for high performance computing. Parallel architectures for vision
• Abstracts: Computational geometry and computer graphics. Relative neighborhood graphs and their relatives

This website is not affiliated with document authors or copyright owners. This page is provided for informational purposes only. Unintentional errors are possible.