Minimizing the diameter of a spanning tree for imprecise points

DOI10.1007/S00453-017-0292-6MaRDI QIDQ1709600zbMATH OpenOpenAlexFDO

Authors Chih-Hung Liu, Sandro Montanari

Publication date 6 April 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0292-6

zbMATH Keywords

imprecise datacomputational geometryVoronoi diagramsminimum diameter spanning trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Minimizing the diameter of a spanning tree for imprecise points
• Minimum Diameter Spanning Trees and Related Problems
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Approximate minimum diameter
• A fully polynomial time approximation scheme for the smallest diameter of imprecise points

Cites work

• scientific article; zbMATH DE number 6693709 (Why is no real title available?)
• scientific article; zbMATH DE number 3987351 (Why is no real title available?)
• scientific article; zbMATH DE number 1555916 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• Applications of random sampling in computational geometry. II
• Computing a (1+)-approximate geometric minimum-diameter spanning tree
• Concrete and abstract Voronoi diagrams
• Constructing strongly convex approximate hulls with inaccurate primitives
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Delaunay triangulation of imprecise points in linear time after preprocessing
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• Facility location and the geometric minimum-diameter spanning tree.
• Farthest-polygon Voronoi diagrams
• Largest and smallest convex hulls for imprecise points
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Maintenance of configurations in the plane
• Minimizing the diameter of a spanning tree for imprecise points
• Minimum Diameter Spanning Trees and Related Problems
• On minimum-and maximum-weight minimum spanning trees with neighborhoods
• Preprocessing Imprecise Points and Splitting Triangulations
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods
• Semi-Online Maintenance of Geometric Optima and Measures
• Systems of distant representatives
• The Clarkson–Shor Technique Revisited and Extended
• Unions of onions: preprocessing imprecise points for fast onion decomposition
• Voronoi diagrams and Delaunay triangulations

Cited in

(4)

• Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree
• Preclustering algorithms for imprecise points
• A fully polynomial time approximation scheme for the smallest diameter of imprecise points
• Minimizing the diameter of a spanning tree for imprecise points

This page was built for publication: Minimizing the diameter of a spanning tree for imprecise points

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