An exact algorithm for the minimum dilation triangulation problem

DOI10.1007/S10898-017-0517-XzbMATH Open1381.90092OpenAlexW2605639086MaRDI QIDQ1679486FDOQ1679486

Authors Sattar Sattari, Mohammad Izadi

Publication date 9 November 2017

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-017-0517-x

zbMATH Keywords

triangulationdilationbranch and bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Upper bounds for minimum dilation triangulation in two special cases
• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• Computing minimum dilation spanning trees in geometric graphs
• A Quadratic Time Algorithm for the Minmax Length Triangulation
• New results for the minimum weight triangulation problem

Cites work

• scientific article; zbMATH DE number 140458 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 6792401 (Why is no real title available?)
• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• An exact algorithm for the minimum dilation triangulation problem
• Computing a minimum-dilation spanning tree is NP-hard
• Computing geometric minimum-dilation graphs is NP-hard
• Delaunay graphs are almost as good as complete graphs
• Geometric Spanner Networks
• Lower bounds on the dilation of plane spanners
• On degrees in random triangulations of point sets
• On stable line segments in all triangulations of a planar point set
• TSPLIB—A Traveling Salesman Problem Library
• The computational geometry algorithms library CGAL
• The stretch factor of the Delaunay triangulation is less than 1.998
• There are planar graphs almost as good as the complete graph

Cited in

(9)

• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• An exact algorithm for constructing minimum Euclidean skeletons of polygons
• Solutions to the Minimum Variance Problem Using Delaunay Triangulation
• scientific article; zbMATH DE number 1305489 (Why is no real title available?)
• An exact algorithm for the minimum dilation triangulation problem
• An algorithm for constructing locally optimal min-max triangulation
• An efficient algorithm for the three-dimensional diameter problem
• Upper bounds for minimum dilation triangulation in two special cases
• An improved upper bound on dilation of regular polygons

Describes a project that uses

Uses Software

• CGAL
• TSPLIB

This page was built for publication: An exact algorithm for the minimum dilation triangulation problem

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