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

A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time

โœ Scribed by N. M. Amato; M. T. Goodrich; E. A. Ramos

Publisher
Springer
Year
2001
Tongue
English
Weight
220 KB
Volume
26
Category
Article
ISSN
0179-5376

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Simple Linear Time Algorithm for Trian
A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
โœ H. Bodlaender; T. Kloks ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 560 KB

In this paper we consider the problem of determining whether a given colored graph can be triangulated, such that no edges between vertices of the same color are added. This problem originated from the perfect phylogeny problem from molecular biology and is strongly related with the problem of recog

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.