Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D

DOI10.1007/s00454-007-9019-9zbMath1138.68043OpenAlexW2068790848MaRDI QIDQ2482197

Stefan Langerman, Michael Soss, Pat Morin, Christian Knauer, Rolf Klein, Micha Sharir, Pankaj K. Agarwal

Publication date: 16 April 2008

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

Full work available at URL: https://doi.org/10.1007/s00454-007-9019-9

zbMATH Keywords

Hopcroft's problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Classical curve theory in normed planes ⋮ Linear time algorithm for optimal feed-link placement ⋮ Testing Euclidean Spanners ⋮ Bottleneck detour tree of points on a path ⋮ Approximating the Packedness of Polygonal Curves ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ Unnamed Item ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Geometric dilation of closed curves in normed planes ⋮ Light orthogonal networks with constant geometric dilation ⋮ Lattice spanners of low degree ⋮ On the Stretch Factor of Polygonal Chains ⋮ Approximating the packedness of polygonal curves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• Range searching with efficient hierarchical cuttings
• \(\epsilon\)-nets and simplex range queries
• A sweepline algorithm for Voronoi diagrams
• On the general motion-planning problem with two degrees of freedom
• A fast algorithm for approximating the detour of a polygonal chain.
• Geometric applications of a randomized optimization technique
• New lower bounds for Hopcroft's problem
• Competitive online routing in geometric graphs
• Comparison of distance measures for planar curves
• Almost tight upper bounds for vertical decompositions in four dimensions
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Self-approaching curves
• Curves with increasing chords
• Applications of Parametric Searching in Geometric Optimization
• Approximating the Stretch Factor of Euclidean Graphs
• Generalized self-approaching curves

This page was built for publication: Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D