𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon

✍ Scribed by Piotr Berman; Andrzej Lingas

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
756 KB
Volume
174
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 and O(n log log n/log n)-processor CRCW PRAM algorithm for the construction of the medial axis of a convex polygon. Our algorithms use the solution to the duration-unknown task scheduling problem due to Cole and Vi&kin and the optimal parallel algorithm for the convex hull of a polygon due to Wagener. They are randomized in the sense that for any given 1 > 0 they terminate in time O(logn) with probability greater than 1 -n-'.

πŸ“œ SIMILAR VOLUMES

An Optimal Algorithm for the Intersectio
An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
✍ Shreesh Jadhav; Asish Mukhopadhyay; Binay Bhattacharya πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 224 KB

The intersection radius of a finite collection of geometrical objects in the plane is the radius of the smallest closed disk that intersects all the objects in the collection. Bhattacharya et al. showed how the intersection radius can be found in linear time for a collection of line segments in the

A sweepline algorithm for Euclidean Voro
A sweepline algorithm for Euclidean Voronoi diagram of circles
✍ Li Jin; Donguk Kim; Lisen Mu; Deok-Soo Kim; Shi-Min Hu πŸ“‚ Article πŸ“… 2006 πŸ› Elsevier Science 🌐 English βš– 647 KB

Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed