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.004zbMATH Open1098.65026OpenAlexW2021972984MaRDI QIDQ2489546FDOQ2489546
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Cites Work
- Triangulating a simple polygon in linear time
- Delaunay graphs are almost as good as complete graphs
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- Classes of graphs which approximate the complete Euclidean graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fast algorithm for approximating the detour of a polygonal chain.
- Approximating the Stretch Factor of Euclidean Graphs
- Computing minimum length paths of a given homotopy class
- Title not available (Why is that?)
- Algorithms and Computation
Cited In (3)
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)
