The geometric dilation of finite point sets

DOI10.1007/S00453-005-1203-9MaRDI QIDQ2492632zbMATH OpenOpenAlexFDO

Authors Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein

Publication date 14 June 2006

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-005-1203-9

zbMATH Keywords

embedded planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Algorithms and Computation
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
• Most finite point sets in the plane have dilation \(>1\)
• Algorithms and Computation
• On the geometric dilation of closed curves, graphs, and point sets

Cited in

(29)

• Geometric dilation of closed curves in normed planes
• Light orthogonal networks with constant geometric dilation
• Beta-skeletons have unbounded dilation
• Dilation coefficient, plane-width, and resolution coefficient of graphs
• Most finite point sets in the plane have dilation \(>1\)
• Quadrisecants give new lower bounds for the ropelength of a knot
• Lattice spanners of low degree
• Lattice spanners of low degree
• Connect the Dot: Computing Feed-Links with Minimum Dilation
• Dilation-free graphs in thel1 metric
• Computing geometric minimum-dilation graphs is NP-hard
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• On plane geometric spanners: a survey and open problems
• Linear time algorithm for optimal feed-link placement
• scientific article; zbMATH DE number 6404003 (Why is no real title available?)
• Algorithms and Computation
• The geometric dilation of three points
• Balls minimize trace constants in BV
• Dilation-optimal edge deletion in polygonal cycles
• Algorithms and Data Structures
• Minimum weight convex Steiner partitions
• Lower bounds on the dilation of plane spanners
• Algorithms and Computation
• Algorithms and Computation
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• On the dilation spectrum of paths, cycles, and trees
• On the geometric dilation of closed curves, graphs, and point sets
• Geometric dilation of closed planar curves: New lower bounds
• Sparse geometric graphs with small dilation

This page was built for publication: The geometric dilation of finite point sets

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