𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On convex segments in a triangulation

✍ Scribed by Yaakov S Kupitz

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
468 KB
Volume
120
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A segment (= l-cell) of a planar triangulation 0 is conuex if it is common to two triangles (2-cells) whose union is a convex set. We determine the maximal number of convex segments of a triangulation over all triangulations CJ having n boundary vertices and m inner vertices (n > 3, m >O).

πŸ“œ SIMILAR VOLUMES

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.