Minimum weight convex Steiner partitions

DOI10.1007/S00453-009-9329-9zbMATH Open1218.05124OpenAlexW1988573007MaRDI QIDQ548652FDOQ548652

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

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

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)

Cites Work

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

Cited In (3)

• Approximation Algorithms for the Minimum Convex Partition Problem
• Euclidean Steiner Spanners: Light and Sparse
• On the total perimeter of homothetic convex bodies in a convex container

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)