Minimum weight convex Steiner partitions

DOI10.1007/S00453-009-9329-9MaRDI QIDQ548652zbMATH OpenOpenAlexFDO

Authors 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

network designSteiner pointsstretch factorconvex partition

Mathematics Subject Classification ID

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

Recommendations

• Approximation Algorithms for the Minimum Convex Partition Problem
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Minimum convex partition of point sets
• Minimum weight pseudo-triangulations
• Minimum convex partition of a constrained point set

Cites work

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

Cited in

(3)

• Euclidean Steiner spanners: light and sparse
• Minimum convex partitions and maximum empty polytopes
• Approximation Algorithms for the Minimum Convex Partition Problem

Describes a project that uses

Uses Software

• LEDA

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

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