Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric

DOI10.1016/j.comgeo.2009.04.005zbMath1225.05077OpenAlexW2011577667MaRDI QIDQ1037776

Victor Alvarez, Raimund Seidel

Publication date: 16 November 2009

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Hausdorff metricapproximation algorithmscoresetsminimum weight spanning tree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Euclidean minimum spanning trees and bichromatic closest pairs
• Approximating extent measures of points
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric