๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A linear-time algorithm for computing the voronoi diagram of a convex polygon

โœ Scribed by Alok Aggarwal; Leonidas J. Guibas; James Saxe; Peter W. Shor

Publisher
Springer
Year
1989
Tongue
English
Weight
906 KB
Volume
4
Category
Article
ISSN
0179-5376

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

A linear-time near-optimum-length triang
A linear-time near-optimum-length triangulation algorithm for convex polygons
โœ Vitit Kantabutra ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 400 KB

This paper shows how to compute a short triangulation for a convex polygon in O(n) time, where n is the number of sides of the input polygon. The resulting triangulation is guaranteed to be of a total length that is only a constant factor of the shortest possible.