Minimizing the diameter of a spanning tree for imprecise points
From MaRDI portal
Publication:1709600
DOI10.1007/s00453-017-0292-6zbMath1390.68722OpenAlexW2912516824MaRDI QIDQ1709600
Sandro Montanari, Chih-Hung Liu
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Farthest-polygon Voronoi diagrams
- Preprocessing imprecise points for Delaunay triangulation: simplified and extended
- Largest and smallest convex hulls for imprecise points
- A linear-time algorithm for computing the Voronoi diagram of a convex polygon
- Delaunay triangulation of imprecise points in linear time after preprocessing
- Maintenance of configurations in the plane
- Concrete and abstract Voronoi diagrams
- Facility location and the geometric minimum-diameter spanning tree.
- Systems of distant representatives
- Applications of random sampling in computational geometry. II
- Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
- Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
- Largest bounding box, smallest diameter, and related problems on imprecise points
- Constructing strongly convex approximate hulls with inaccurate primitives
- On Minimum-and Maximum-Weight Minimum Spanning Trees with Neighborhoods
- Voronoi Diagrams and Delaunay Triangulations
- [https://portal.mardi4nfdi.de/wiki/Publication:2968106 Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition]
- Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods
- Minimizing the Diameter of a Spanning Tree for Imprecise Points
- Minimum Diameter Spanning Trees and Related Problems
- FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
- Semi-Online Maintenance of Geometric Optima and Measures
- The Clarkson–Shor Technique Revisited and Extended
- An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
- Preprocessing Imprecise Points and Splitting Triangulations
