Name
Abstract | ||
|---|---|---|
Every pair of points lying on a polygonal path P in the plane has a detour associated with it, which is the ratio between their distance along the path and their Euclidean distance. Given a set S of points along the path, this information can be encoded in a weighted complete graph on S. Among all spanning trees on this graph, a bottleneck spanning tree is one whose maximum edge weight is minimum. We refer to such a tree as a bottleneck detour tree of S. In other words, a bottleneck detour tree of S is a spanning tree in which the maximum detour (with respect to the original path) between pairs of adjacent points is minimum. We show how to find a bottleneck detour tree in expected O(nlog3n+m) time, where P consists of m edges and |S|=n. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.comgeo.2019.01.005 | Computational Geometry |
Keywords | Field | DocType |
Polygonal path,Detour,Bottleneck spanning tree,Randomized algorithm | Discrete mathematics,Complete graph,Graph,Bottleneck,Polygon,Combinatorics,Euclidean distance,Spanning tree,Mathematics | Journal |
Volume | ISSN | Citations |
79 | 0925-7721 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Greg Aloupis | 1 | 200 | 26.50 |
| Paz Carmi | 2 | 321 | 43.14 |
| Lilach Chaitman-Yerushalmi | 3 | 16 | 4.72 |
| Matthew J. Katz | 4 | 225 | 19.92 |
| Stefan Langerman | 5 | 831 | 101.66 |