Geometric spanners for weighted point sets

DOI10.1007/S00453-010-9465-2MaRDI QIDQ634687zbMATH OpenOpenAlexFDO

Authors Mohammad A. Abam, Mohammad Farshi, Joachim Gudmundsson, Mark de Berg, Michiel Smid

Publication date 16 August 2011

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-010-9465-2

zbMATH Keywords

computational geometrydoubling dimensiongeodesic metricgeometric spannerssemi-separated pair decompositionwell-separated pair decomposition

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Geometric Spanners for Weighted Point Sets
• Spanners of Additively Weighted Point Sets
• Spanners of additively weighted point sets
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points

Cites work

• scientific article; zbMATH DE number 437554 (Why is no real title available?)
• scientific article; zbMATH DE number 3261634 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximating shortest paths on a convex polytope in three dimensions
• Balanced aspect ratio trees: Combining the advantages of \(k\)-\(d\) trees and octrees
• Bypassing the embedding
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Fully dynamic geometric spanners
• Geometric Spanner Networks
• Lectures on analysis on metric spaces
• New constructions of SSPDs and their applications
• On separating systems
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Region-fault tolerant geometric spanners
• Searching dynamic point sets in spaces with bounded doubling dimension
• Spanners of Additively Weighted Point Sets

Cited in

(16)

• Spanners of Additively Weighted Point Sets
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Geometric Spanners for Points Inside a Polygonal Domain
• Geodesic spanners for points on a polyhedral terrain
• New constructions of SSPDs and their applications
• Geometric Spanners for Weighted Point Sets
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes
• Spanners for geodesic graphs and visibility graphs
• On the power of the semi-separated pair decomposition
• Geodesic spanners for points on a polyhedral terrain
• Fault-tolerant additive weighted geometric spanners
• Spanners of additively weighted point sets
• scientific article; zbMATH DE number 4153914 (Why is no real title available?)
• Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets
• Vertex fault-tolerant spanners for weighted points in polygonal domains

This page was built for publication: Geometric spanners for weighted point sets

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