Parallel triangulation of a polygon in two calls to the trapezoidal map

DOI10.1007/BF01762118MaRDI QIDQ1104087zbMATH OpenOpenAlexFDO

Authors Chee K. Yap

Publication date 1988

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01762118

zbMATH Keywords

computational geometryparallel algorithmtrapezoidal map algorithmtriangulation of simple polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Triangulating a polygon in parallel
• scientific article; zbMATH DE number 4074480
• scientific article; zbMATH DE number 512921
• Orthogonal triangulation of polygons
• scientific article; zbMATH DE number 219273
• On triangulation axes of polygons
• Parallel enumeration of triangulations
• Rectangulating rectilinear polygons in parallel
• Rectangulating rectilinear polygons in parallel
• Parallel Delaunay triangulation in three dimensions

Cites work

• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity

Cited in

(17)

• Optimal parallel algorithms for point-set and polygon problems
• Parallel methods for visibility and shortest-path problems in simple polygons
• Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
• Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons
• Optimal cooperative search in fractional cascaded data structures
• On the multisearching problem for hypercubes
• Intelligent computing systems with actors -- parallel dynamic programming algorithm of the polygon triangulation problem
• On parallel complexity of planar triangulations
• scientific article; zbMATH DE number 4074480 (Why is no real title available?)
• scientific article; zbMATH DE number 512921 (Why is no real title available?)
• Quadrilaterizing an Orthogonal Polygon in Parallel
• Determining Weak Visibility of a Polygon from an Edge in Parallel
• AN IMPROVED HYPERCUBE BOUND FOR MULTISEARCHING AND ITS APPLICATIONS
• scientific article; zbMATH DE number 219273 (Why is no real title available?)
• Triangulating a polygon in parallel
• Testing a simple polygon for monotonicity optimally in parallel
• Planar separators and parallel polygon triangulation.

This page was built for publication: Parallel triangulation of a polygon in two calls to the trapezoidal map

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104087)