A linear time algorithm for max-min length triangulation of a convex polygon
From MaRDI portal
Publication:845931
DOI10.1016/J.IPL.2006.09.014zbMATH Open1184.68563OpenAlexW2044408057MaRDI QIDQ845931FDOQ845931
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
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
- Maximum weight triangulation and graph drawing
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- A quasi-polynomial time approximation scheme for minimum weight triangulation
- A Quadratic Time Algorithm for the Minmax Length Triangulation
- Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
- A lower bound for \(\beta\)-skeleton belonging to minimum weight triangulations
- Edge insertion for optimal triangulations
- A linear-time approximation scheme for maximum weight triangulation of convex polygons
- Algorithms for optimal area triangulations of a convex polygon
- Minimum weight triangulation is NP-hard
- Computing and Combinatorics
- ON ENUMERATING AND SELECTING DISTANCES
- DIAMONDS ARE NOT A MINIMUM WEIGHT TRIANGULATION'S BEST FRIEND
- On \(\beta\)-skeleton as a subgraph of 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
- Title not available (Why is that?)
- 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)
