A linear time algorithm for max-min length triangulation of a convex polygon

DOI10.1016/j.ipl.2006.09.014zbMath1184.68563OpenAlexW2044408057MaRDI QIDQ845931

Shiyan Hu

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.09.014

zbMATH Keywords

computational geometrymax-min length \(k\)-set triangulationmax-min length triangulation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Maximum weight triangulation and graph drawing
• A linear-time approximation scheme for maximum weight triangulation of convex polygons
• Edge insertion for optimal triangulations
• Algorithms for optimal area triangulations of a convex polygon
• A Quadratic Time Algorithm for the Minmax Length Triangulation
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Computing and Combinatorics
• ON ENUMERATING AND SELECTING DISTANCES
• DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
• On \(\beta\)-skeleton as a subgraph of the minimum weight triangulation

This page was built for publication: A linear time algorithm for max-min length triangulation of a convex polygon