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.
Publication Name: Proceedings of the IEEE
Subject: Electronics
ISSN: 0018-9219
Year: 1992
User Contributions:
Comment about this article or add new information about this topic:
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.
Publication Name: Proceedings of the IEEE
Subject: Electronics
ISSN: 0018-9219
Year: 1992
User Contributions:
Comment about this article or add new information about this topic: