Parallel triangulation of a polygon in two calls to the trapezoidal map
type: Item
instance of: scholarly article
title: Parallel triangulation of a polygon in two calls to the trapezoidal map
zbMATH Open document ID: 0646.68057
DOI: 10.1007/BF01762118
published in: Algorithmica
publication date: 1988-01-01T00:00:00Z
review text: We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best known trapezoidal map algorithm, ours run in time O(log n) using O(n) CREW PRAM processors.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4055043
zbMATH Keywords: parallel algorithm
zbMATH Keywords: triangulation of simple polygon
zbMATH Keywords: computational geometry
zbMATH Keywords: trapezoidal map algorithm
author: Chee K. Yap
MaRDI profile type: MaRDI publication profile
cites work: Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
cites work: Triangulation and shape-complexity
cites work: Triangulating Simple Polygons and Equivalent Problems
full work available at URL: https://doi.org/10.1007/bf01762118
OpenAlex ID: W2092472617
Recommended article: Triangulating a polygon in parallel
Recommended article: Q3805897
Recommended article: Q4281634
Recommended article: Orthogonal triangulation of polygons
Recommended article: Q4694760
Recommended article: On triangulation axes of polygons
Recommended article: Parallel enumeration of triangulations
Recommended article: Rectangulating rectilinear polygons in parallel
Recommended article: Parallel Delaunay triangulation in three dimensions
description: scientific article; zbMATH DE number 4055043