Parallel computational geometry (Q1115600): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Alok Aggarwal / rank | |||
Property / author | |||
Property / author: Colm P. O'Dunlaing / rank | |||
Property / author | |||
Property / author: Chee-Keng Yap / rank | |||
Property / reviewed by | |||
Property / reviewed by: Hans-Dietrich Hecker / rank | |||
Revision as of 10:15, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel computational geometry |
scientific article |
Statements
Parallel computational geometry (English)
0 references
1988
0 references
This paper contributes efficient parallel algorithms for solving some basic geometric problems. ``Efficient'' here means polylogarithmic in parallel time. All the algorithmus presented are algorithms executable in polylog depth on polynomial-size circuits. Such algorithms usually are called NC-algorithms. Many of the problems considered in this paper are known to have \(\Omega\) (n log n) lower bounds in the algebraic computation tree model. Standard techniques in the subject such as contour-tracing, plane-sweeping and gift-wrapping initially seem inherently sequential. One of the main contributions of the paper is to show that NC-analogues of these techniques actually exist. Some of the problems of planar convex hulls, planar Voronoi-diagrams and three-dimensional convex hulls (with the same \(\Theta\) (n log n) sequential time complexity) are shown to be in \(NC^+_ 1(n)\), \(NC^+_ 2(n)\), \(NC^+_ 3(n)\), respectively. The notation \(NC^+_ k(f(u))\) indicates the class of algorithms running on a PRAM (P for parallel) using f(u) processors and halting in \(O(\log^ k(n))\) steps. Further problems discussed in this paper are other proximity problems, segment intersections, triangulations of polygons, polygon optimization problems and creating data structures in two and three dimensions to answer standard queries.
0 references
computational geometry
0 references
parallel algorithms
0 references
convex hulls
0 references
Voronoi- diagrams
0 references
PRAM
0 references
data structures
0 references