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

DOI10.4230/LIPICS.SOCG.2018.44zbMATH Open1489.68357arXiv1802.06415MaRDI QIDQ5115812FDOQ5115812

Authors: Andreas Haas 

Publication date: 18 August 2020

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

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

zbMATH Keywords

computational geometryminimum-weight triangulation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Computing Area-Optimal Simple Polygonizations
• Title not available (Why is that?)

Uses Software

• CGAL
• TSPLIB

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)