Solving large-scale minimum-weight triangulation instances to provable optimality

DOI10.4230/LIPICS.SOCG.2018.44MaRDI QIDQ5115812zbMATH OpenFDO

Authors Andreas Haas

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1802.06415

zbMATH Keywords

computational geometryminimum-weight triangulation

Mathematics Subject Classification ID

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

Recommendations

• Minimum-weight triangulation is NP-hard
• Polynomial-time instances of the minimum weight triangulation problem
• On a linear program for minimum-weight triangulation
• Minimum weight triangulation is NP-hard
• New results for the minimum weight triangulation problem

Cites work

• scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• scientific article; zbMATH DE number 49455 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases
• A large subgraph of the minimum weight triangulation
• Algorithms and Computation
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• Minimal Triangulations of Polygonal Domains
• Minimum-weight triangulation is NP-hard
• New results on MWT subgraphs
• On exclusion regions for optimal triangulations
• Parameterized and Exact Computation
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(2)

• Edge sparsification for geometric tour problems
• Computing area-optimal simple polygonizations

Describes a project that uses

Uses Software

• TSPLIB
• CGAL

This page was built for publication: Solving large-scale minimum-weight triangulation instances to provable optimality

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