Beta-skeletons have unbounded dilation

DOI10.1016/S0925-7721(01)00055-4MaRDI QIDQ1614068zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 3 September 2002

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/9907031

zbMATH Keywords

dilationgeometric graphsfractal curvesKoch snowflakebeta-skeletons

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation. In particular this applies to the Gabriel graph.

Recommendations

• Sparse geometric graphs with small dilation
• Algorithms and Computation
• Algorithms and Computation
• How \({\beta}\)-skeletons lose their edges
• The geometric dilation of finite point sets

Cites work

• {{#invoke:WikidataIB|getLink|Q3024785}} scientific article; zbMATH DE number 2185620 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q3484375}} scientific article; zbMATH DE number 4155925 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4028874}} scientific article; zbMATH DE number 140458 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4945509}} scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q1327172}} Computing a subgraph of the minimum weight triangulation
• {{#invoke:WikidataIB|getLink|Q584279}} Delaunay graphs are almost as good as complete graphs
• {{#invoke:WikidataIB|getLink|Q1194312}} The \(\gamma\)-neighborhood graph
• {{#invoke:WikidataIB|getLink|Q1823959}} There are planar graphs almost as good as the complete graph

Cited in

(7)

• Incentive compatible and globally efficient position based routing for selfish reverse multicast in wireless sensor networks
• \(\beta\)-skeletons for a set of line segments in \(\mathbb R^2\)
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• Geometric spanners with applications in wireless networks
• On the stretch factor of polygonal chains
• Odd Yao-Yao graphs are not spanners
• scientific article; zbMATH DE number 7561700 (Why is no real title available?)

This page was built for publication: Beta-skeletons have unbounded dilation

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