Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound

DOI10.1007/978-3-319-48749-6_24MaRDI QIDQ2958326zbMATH OpenOpenAlexFDO

Authors Sung Eun Bae, Tong-Wook Shinn, Tadao Takaoka

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Polynomial-time instances of the minimum weight triangulation problem
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• Approximating minimum-weight triangulations in three dimensions
• The minimum weight triangulation problem with few inner points
• Parameterized and Exact Computation
• scientific article; zbMATH DE number 742947
• New results for the minimum weight triangulation problem
• On a linear program for minimum-weight triangulation

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A more efficient algorithm for the min-plus multiplication
• A new upper bound on the complexity of the all pairs shortest path problem
• A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• Improved algorithm for all pairs shortest paths
• Minimal Triangulations of Polygonal Domains
• New Bounds on the Complexity of the Shortest Path Problem
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• On the exponent of all pairs shortest path problem
• P-COMPLETE GEOMETRIC PROBLEMS

Cited in

(2)

• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Finding a maximum weight triangle in n ^3-Δ time, with applications

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound

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