Testing a simple polygon for monotonicity optimally in parallel (Q688449)
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: Testing a simple polygon for monotonicity optimally in parallel |
scientific article; zbMATH DE number 444835
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Testing a simple polygon for monotonicity optimally in parallel |
scientific article; zbMATH DE number 444835 |
Statements
Testing a simple polygon for monotonicity optimally in parallel (English)
0 references
19 May 1994
0 references
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.
0 references
parallel algorithms
0 references
computational geometry
0 references
simple polygons
0 references
