New constructions of SSPDs and their applications

DOI10.1016/J.COMGEO.2011.12.003MaRDI QIDQ419372zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled, Mohammad A. Abam

Publication date 18 May 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2011.12.003

zbMATH Keywords

separatorsgeometric spannersseparated pair decomposition

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• New constructions of SSPDs and their applications
• On the Power of the Semi-Separated Pair Decomposition
• On the power of the semi-separated pair decomposition
• Constructing sparse \(t\)-spanners with small separators.
• The emergence of sparse spanners and well-separated pair decomposition under anarchy

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A practical approach for computing the diameter of a point set
• Applications of a Planar Separator Theorem
• Approximating energy efficient paths in wireless multi-hop networks
• Balanced aspect ratio trees: Combining the advantages of \(k\)-\(d\) trees and octrees
• Classes of graphs which approximate the complete Euclidean graph
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Geometric Spanner Networks
• Geometric spanners for weighted point sets
• Graph separators, with applications
• Lectures on analysis on metric spaces
• On separating systems
• On the Power of the Semi-Separated Pair Decomposition
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Region-fault tolerant geometric spanners
• Separators for sphere-packings and nearest neighbor graphs
• Spanners for Geometric Intersection Graphs

Cited in

(8)

• A spanner for the day after
• Local geometric spanners
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• New constructions of SSPDs and their applications
• A spanner for the day after
• Spanners for geodesic graphs and visibility graphs
• On the power of the semi-separated pair decomposition
• Vertex fault-tolerant spanners for weighted points in polygonal domains

This page was built for publication: New constructions of SSPDs and their applications

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