Testing a simple polygon for monotonicity optimally in parallel
From MaRDI portal
We show that an \(n\)-vertex simple polygon can be tested in parallel for monotonicity optimally in \(O(\log n)\) time using \(n/\log n\) EREW PRAM processors, and we present two different optimal parallel algorithms for solving this problem. Our results leads to an optimal parallel algorithm for triangulating simple polygons that runs in \(O(\log n)\) time using \(n/\log n\) EREW PRAM processors if the polygons are monotone.
Recommendations
Cites work
- A new triangulation-linear class of simple polygons
- Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines
- An optimal parallel algorithm for the minimum circle-cover problem
- Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
- scientific article; zbMATH DE number 1142306 (Why is no real title available?)
- On geodesic properties of polygons relevant to linear time triangulation
- Optimal merging and sorting on the EREW PRAM
- Parallel Merge Sort
- Parallel Prefix Computation
- Parallel triangulation of a polygon in two calls to the trapezoidal map
- Planar separators and parallel polygon triangulation.
- Triangulating a polygon in parallel
Cited in
(2)
This page was built for publication: Testing a simple polygon for monotonicity optimally in parallel
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688449)
