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.004MaRDI QIDQ2489546zbMATH OpenOpenAlexFDO

Authors Christos Levcopoulos, Andrzej Lingas, 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

dilationpolygonpolynomial-time approximation schemetriangulation

Mathematics Subject Classification ID

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

Review text

The dilatation of a plane graph \(G\) is the maximum value of the ratio between the length of a shortest path between two points \(p\) and \(q\) in \(G\) and the Euclidean distance \(d(p,q)\) taken over all pairs of points \(p\) and \(q\) in \(G\). The authors design a fully polynomial-time approximation scheme for the problem of finding a triangulation of a simple polygon with a constant number of sources of dilation that achieves the minimum vertex dilation. Some open problems are formulated.

Recommendations

• An exact algorithm for the minimum dilation triangulation problem
• On the minimality of polygon triangulation
• Upper bounds for minimum dilation triangulation in two special cases
• Approximation for minimum triangulation of convex polyhedra
• A linear-time approximation scheme for minimum weight triangulation of convex polygons
• scientific article; zbMATH DE number 2080989
• An algorithm for dynamic Delaunay triangulation of simple polygon
• A contribution to triangulation algorithms for simple polygons
• An approximate algorithm for the minimal vertex nested polygon problem

Cites work

• A fast algorithm for approximating the detour of a polygonal chain.
• Algorithms and Computation
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Approximating the Stretch Factor of Euclidean Graphs
• Classes of graphs which approximate the complete Euclidean graph
• Computing minimum length paths of a given homotopy class
• Delaunay graphs are almost as good as complete graphs
• scientific article; zbMATH DE number 5542484 (Why is no real title available?)
• scientific article; zbMATH DE number 1947396 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Triangulating a simple polygon in linear time

Cited in

(3)

• An exact algorithm for the minimum dilation triangulation problem
• Dilation-optimal edge deletion in polygonal cycles
• Upper Bound on Dilation of Triangulations of Cyclic Polygons

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

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