scientific article; zbMATH DE number 4016210
[For the entire collection see Zbl 0623.00022.] This paper has two goals. First, we point out that most problems in computational geometry in fact have fast parallel algorithms (that is, in \(NC^*)\) by reduction to the cell decomposition result of Kozen and Yap. We illustrate this using a new notion of generalized Voronoi diagrams that subsumes all known instances. While the existence of NC\({}^*\) algorithms for computational geometry is theoretically significant, it leaves much to be desired for specific problems. Therefore, the second part of the paper surveys some recent results in a fast growing list of parallel algorithms for computational geometry.
- Parallel computational geometry
- Optimal parallel algorithms for point-set and polygon problems
- On the parallel-decomposability of geometric problems
- scientific article; zbMATH DE number 1255658 (Why is no real title available?)
- scientific article; zbMATH DE number 866044 (Why is no real title available?)
- scientific article; zbMATH DE number 1424292 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3028358)