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

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item