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

DOI10.1016/J.IPL.2006.09.014MaRDI QIDQ845931zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A Quadratic Time Algorithm for the Minmax Length Triangulation
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• Quadratic time computable instances of MaxMin and MinMax area triangulations of convex polygons
• Algorithms for optimal area triangulations of a convex polygon
• An $O(n^2 \log n)$ Time Algorithm for the Minmax Angle Triangulation

Cites work

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

Cited in

(12)

• Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Implementation of linear minimum area enclosing triangle algorithm. Application note
• Computing MaxMin edge length triangulations
• An algorithm for constructing locally optimal min-max triangulation
• Quadratic time computable instances of MaxMin and MinMax area triangulations of convex polygons
• Algorithms for optimal area triangulations of a convex polygon
• Two linear-time algorithms for computing the minimum length polygon of a digital contour
• A Quadratic Time Algorithm for the Minmax Length Triangulation
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• scientific article; zbMATH DE number 3932438 (Why is no real title available?)
• Computing MaxMin edge length triangulations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845931)