Tight bounds for connecting sites across barriers

DOI10.1007/S00454-007-9025-YzbMath1170.68041OpenAlexW2033123200MaRDI QIDQ958235

Csaba D. Tóth, Diane L. Souvaine, Eynat Rafalin, David W. Krumme

Publication date: 2 December 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-007-9025-y

zbMATH Keywords

crossing numberspanning trees

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Inequalities and extremum problems involving convexity in convex geometry (52A40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Convex Partitions with 2-Edge Connected Dual Graphs ⋮ Convex partitions with 2-edge connected dual graphs ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Tight bounds for connecting sites across barriers

Cites Work

• Linear-time reconstruction of Delaunay triangulations with applications
• Tight bounds for connecting sites across barriers
• Efficient partition trees
• Spanning trees crossing few barriers
• Quasi-optimal range searching in spaces of finite VC-dimension
• Spanning trees with low crossing number
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions

This page was built for publication: Tight bounds for connecting sites across barriers