An optimal parallel algorithm for triangulating a set of points in the plane
type: Item
instance of: scholarly article
title: An optimal parallel algorithm for triangulating a set of points in the plane
zbMATH Open document ID: 0641.68068
DOI: 10.1007/BF01414464
author: Ed Merks
published in: International Journal of Parallel Programming
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 52A10
zbMATH DE Number: 4045152
zbMATH Keywords: computatioal geometry
zbMATH Keywords: convex hull
zbMATH Keywords: parallel algorithm
zbMATH Keywords: CREW PRAM
zbMATH Keywords: lower bound
zbMATH Keywords: triangulation
zbMATH Keywords: divide-and-conquer
MaRDI profile type: Publication
cites work: Automatic triangulation of arbitrary planar domains for the finite element method
cites work: An optimal speed-up parallel algorithm for triangulating simplicial point sets in space
cites work: Parallelism in random access machines
cites work: Sorting in \(c \log n\) parallel steps
Recommended article: Optimal parallel algorithms for point-set and polygon problems
Recommended article: On parallel complexity of planar triangulations
Recommended article: A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES
Recommended article: Q4247271
Recommended article: Q4500844
Recommended article: An optimal parallel algorithm for the visibility of a simple polygon from a point
Recommended article: An efficient parallel algorithm for planarity
Recommended article: Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane
Recommended article: Optimal randomized parallel algorithms for computational geometry
description: scientific article; zbMATH DE number 4045152