An optimal parallel algorithm for triangulating a set of points in the plane (Q1100899)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An optimal parallel algorithm for triangulating a set of points in the plane |
scientific article; zbMATH DE number 4045152
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An optimal parallel algorithm for triangulating a set of points in the plane |
scientific article; zbMATH DE number 4045152 |
Statements
An optimal parallel algorithm for triangulating a set of points in the plane (English)
0 references
1986
0 references
This paper presents an optimal parallel algorithm for triangulating an arbitrary set of n points in the plane. The algorithm runs in O(log n) time using O(n) space and O(n) processors on a concurrent-read, exclusive-write parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is \(\Omega\) (log n) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into \(\sqrt{n}\) subproblems is employed.
0 references
computatioal geometry
0 references
convex hull
0 references
parallel algorithm
0 references
CREW PRAM
0 references
lower bound
0 references
triangulation
0 references
divide-and-conquer
0 references
0.9431891
0 references
0.9171096
0 references
0.9169191
0 references
0.91213095
0 references
0.9104715
0 references
0.90875864
0 references
