𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel algorithms for some functions of two convex polygons

✍ Scribed by Mikhail J. Atallah; Michael T. Goodrich

Publisher
Springer
Year
1988
Tongue
English
Weight
712 KB
Volume
3
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A nearly optimal parallel algorithm for
A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon
✍ Piotr Berman; Andrzej Lingas πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 756 KB

We present a parallel algorithm for the Voronoi diagram of the set of vertices of a convex polygon. The algorithm runs in time O(logn) and uses O(n loglogn/log n) processors in the CRCW PRAM model. The concurrent write is used only by an integer sorting subroutine. We also obtain an O(log n)-time an

Efficient algorithm for transversal of d
Efficient algorithm for transversal of disjoint convex polygons
✍ Francis Y.L. Chin; Fu Lee Wang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 103 KB

Given a set S of n disjoint convex polygons {P i | 1 i n} in a plane, each with k i vertices, the transversal problem is to determine whether there exists a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N + n log n) time, where N = n i=1