Parallel geometric algorithms on a mesh-connected computer
The authors show that a number of geometric problems can be solved on a \(\sqrt{n}\times \sqrt{n}\)-mesh-connected computer (single instruction stream, multiple data stream) in O(\(\sqrt{n})\) time which is asymptotically optimal. The algorithms are based on the divide-and- conquer problem-solving strategy. Trapezoidal decomposition and planar point location problems are solved by a direct application of the multipoint location algorithm. The authors show that the Voronoi diagram can be computed in O(\(\sqrt{n})\) time. With the help of this result many other interesting algorithms for geometric problems has been obtained.
- Parallel Voronoi diagram in \(L_ 1(L_{\infty})\) metric on a mesh- connected computer
- scientific article; zbMATH DE number 4170139
- Parallel computational geometry
- An improved parallel algorithm for constructing Voronoi diagram on a mesh-connected computer
- On the parallel-decomposability of geometric problems
- A Self-Routing Benes Network and Parallel Permutation Algorithms
- An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes
- An optimal routing algorithm for mesh-connected Parallel computers
- Bitonic Sort on a Mesh-Connected Parallel Computer
- Finding Connected Components and Connected Ones on a Mesh-Connected Parallel Computer
- Graph Problems on a Mesh-Connected Processor Array
- Parallel computational geometry
- Sorting on a mesh-connected parallel computer
- Two-Dimensional Voronoi Diagrams in the L p -Metric
- Voronoi diagrams from convex hulls
- An efficient VLSI architecture with applications to geometric problems
- An improved parallel algorithm for constructing Voronoi diagram on a mesh-connected computer
- On the parallel-decomposability of geometric problems
- Fine-grain discrete Voronoi diagram algorithms in \(L_1\) and \(L_\infty\) norms
- A parallel algorithm for volume projections on SIMD mesh-connected computers
- Triangulation on reconfigurable meshes: A natural decomposition approach
- Voronoi-like partition of lattice in cellular automata
- Recursion and parallel algorithms in geometric modeling problems
- An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram
- scientific article; zbMATH DE number 4170139 (Why is no real title available?)
- scientific article; zbMATH DE number 4066315 (Why is no real title available?)
- scientific article; zbMATH DE number 1255658 (Why is no real title available?)
- AN OPTIMAL PARALLEL ALGORITHM FOR FINDING THE SMALLEST ENCLOSING TRIANGLE ON A MESH-CONNECTED COMPUTER∗
- Dynamic computational geometry on meshes and hypercubes
- Simulating parallel neighboring communications among square meshes and square toruses
- Efficiently parallelised algorithm to find isoptic surface of polyhedral meshes
- Parallel Voronoi diagram in \(L_ 1(L_{\infty})\) metric on a mesh- connected computer
This page was built for publication: Parallel geometric algorithms on a mesh-connected computer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825643)
