Most finite point sets in the plane have dilation \(>1\)

DOI10.1007/s00454-014-9651-0zbMath1312.52009OpenAlexW1983769376MaRDI QIDQ2256585

Martin Kuetz, Rainer Penninger, Rolf Klein

Publication date: 19 February 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-014-9651-0

zbMATH Keywords

dilationgeometric graphcomputational geometrydetourstretch factorspanning ratio

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Erd?s problems and related topics of discrete geometry (52C10)

Related Items (3)

Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lattice spanners of low degree

Cites Work

• Unnamed Item
• Unnamed Item
• On the geometric dilation of closed curves, graphs, and point sets
• Minimum dilation stars
• Geometric dilation of closed planar curves: New lower bounds
• Sparse geometric graphs with small dilation
• Classes of graphs which approximate the complete Euclidean graph
• A fast algorithm for approximating the detour of a polygonal chain.
• A dense planar point set from iterated line intersections.
• On the density of iterated line segment intersections
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• The geometric dilation of finite point sets
• Geometric Spanner Networks
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
• Algorithms and Data Structures

This page was built for publication: Most finite point sets in the plane have dilation \(>1\)