A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation

DOI10.1016/j.comgeo.2005.06.004zbMath1098.65026OpenAlexW2021972984MaRDI QIDQ2489546

Andrzej Lingas, Christos Levcopoulos, Rolf Klein

Publication date: 28 April 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2005.06.004

zbMATH Keywords

triangulationpolygondilationpolynomial-time approximation scheme

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

An exact algorithm for the minimum dilation triangulation problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon in linear time
• Classes of graphs which approximate the complete Euclidean graph
• Computing minimum length paths of a given homotopy class
• A fast algorithm for approximating the detour of a polygonal chain.
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Approximating the Stretch Factor of Euclidean Graphs
• Algorithms and Computation

This page was built for publication: A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation