scientific article; zbMATH DE number 4016210

From MaRDI portal
Publication:3028358





[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.











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)