Spanning trees crossing few barriers

DOI10.1007/s00454-003-2853-5zbMath1033.68078OpenAlexW2146448055WikidataQ56970639 ScholiaQ56970639MaRDI QIDQ1422228

Leonidas J. Guibas, Hisao Tamaki, Tetsuo Asano, Mark T. de Berg, Otfried Schwarzkopf, Jack Scott Snoeyink

Publication date: 5 February 2004

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

Full work available at URL: https://doi.org/10.1007/s00454-003-2853-5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Cuttings for disks and axis-aligned rectangles in three-space ⋮ Tight bounds for connecting sites across barriers ⋮ Binary plane partitions for disjoint line segments ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique

Cites Work

• Unnamed Item
• Unnamed Item
• Linear-time reconstruction of Delaunay triangulations with applications
• Efficient binary space partitions for hidden-surface removal and solid modeling
• On the optimal binary plane partition for sets of isothetic rectangles
• Ray shooting, depth orders and hidden surface removal
• Linear size binary space partitions for uncluttered scenes
• Quasi-optimal range searching in spaces of finite VC-dimension
• Realistic input models for geometric algorithms
• Optimal Point Location in a Monotone Subdivision
• Illumination of convex discs