✦ LIBER ✦

A fast las vegas algorithm for triangulating a simple polygon

✍ Scribed by Kenneth L. Clarkson; Robert E. Tarjan; Christopher J. Wyk

Publisher: Springer
Year: 1989
Tongue: English
Weight: 572 KB
Volume: 4
Category: Article
ISSN: 0179-5376
DOI: 10.1007/bf02187741

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Randomized Algorithm for Triangulating

A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time

✍ N. M. Amato; M. T. Goodrich; E. A. Ramos 📂 Article 📅 2001 🏛 Springer 🌐 English ⚖ 220 KB

A simple and fast incremental randomized

A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

✍ Raimund Seidel 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 881 KB

A new linear algorithm for triangulating

A new linear algorithm for triangulating monotone polygons

✍ Godfried T Toussaint 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 258 KB

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 simple quality triangulation algorithm

A simple quality triangulation algorithm for complex geometries

✍ Yaoxin Zhang; Yafei Jia; H. C. Chan; Sam S. Y. Wang 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 642 KB

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.