A fast algorithm for approximating the detour of a polygonal chain.

DOI10.1016/S0925-7721(03)00046-4zbMath1045.65017MaRDI QIDQ1428113

Andrzej Lingas, Rolf Klein, Annette Ebbers-Baumann, Elmar Langetepe

Publication date: 14 March 2004

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

zbMATH Keywords

algorithmapproximationdilationpolygonal chainsmaximum detour

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Length, area, volume and convex sets (aspects of convex geometry) (52A38)

Related Items (13)

EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION ⋮ On the geometric dilation of closed curves, graphs, and point sets ⋮ Geometric dilation of closed planar curves: New lower bounds ⋮ Linear time algorithm for optimal feed-link placement ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Light orthogonal networks with constant geometric dilation ⋮ Lattice spanners of low degree

Cites Work

• Unnamed Item
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• An optimal visibility graph algorithm for triangulated simple polygons
• Classes of graphs which approximate the complete Euclidean graph
• Perspectives of Monge properties in optimization
• Self-approaching curves
• Curves with increasing chords
• Approximating the Stretch Factor of Euclidean Graphs
• Generalized self-approaching curves

This page was built for publication: A fast algorithm for approximating the detour of a polygonal chain.