An exact algorithm for the minimum dilation triangulation problem
From MaRDI portal
Publication:1679486
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
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
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Cites Work
- TSPLIB—A Traveling Salesman Problem Library
- Geometric Spanner Networks
- There are planar graphs almost as good as the complete graph
- Delaunay graphs are almost as good as complete graphs
- The computational geometry algorithms library CGAL
- On stable line segments in all triangulations of a planar point set
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Computing a minimum-dilation spanning tree is NP-hard
- Title not available (Why is that?)
- The stretch factor of the Delaunay triangulation is less than 1.998
- On degrees in random triangulations of point sets
- Title not available (Why is that?)
- An exact algorithm for the minimum dilation triangulation problem
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- Computing geometric minimum-dilation graphs is NP-hard
- Title not available (Why is that?)
- Lower bounds on the dilation of plane spanners
Cited In (9)
- An exact algorithm for constructing minimum Euclidean skeletons of polygons
- An improved upper bound on dilation of regular polygons
- Solutions to the Minimum Variance Problem Using Delaunay Triangulation
- An algorithm for constructing locally optimal min-max triangulation
- An exact algorithm for the minimum dilation triangulation problem
- 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
- Title not available (Why is that?)
- An efficient algorithm for the three-dimensional diameter problem
Uses Software
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)
