Minimum weight convex Steiner partitions

DOI10.1007/s00453-009-9329-9zbMath1218.05124OpenAlexW1988573007MaRDI QIDQ548652

Adrian Dumitrescu, Csaba D. Tóth

Publication date: 30 June 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9329-9

zbMATH Keywords

Steiner pointsnetwork designstretch factorconvex partition

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

Euclidean Steiner Spanners: Light and Sparse ⋮ On the total perimeter of homothetic convex bodies in a convex container

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some results on greedy embeddings in metric spaces
• Constructing plane spanners of bounded degree and low weight
• Light orthogonal networks with constant geometric dilation
• A note on Delaunay and optimal triangulations
• Classes of graphs which approximate the complete Euclidean graph
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• Approximating the minimum weight Steiner triangulation
• Provably good mesh generation
• Ray shooting in polygons using geodesic triangulations
• Competitive online routing in geometric graphs
• A note on convex decompositions of a set of points in the plane
• Minimum weight pseudo-triangulations
• The geometric dilation of finite point sets
• On a conjecture related to geometric routing
• Geometric Spanner Networks
• Minimum-weight triangulation is NP-hard
• A heuristic triangulation algorithm
• Minimal Triangulations of Polygonal Domains
• Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation
• Online Routing in Triangulations
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Steiner Minimal Trees
• Approximation Algorithms for the Minimum Convex Partition Problem
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Routing with guaranteed delivery in ad hoc wireless networks

This page was built for publication: Minimum weight convex Steiner partitions