Content deleted Content added
→top: fine, put optimality of 2d in lead |
better? |
||
Line 14:
*The [[Steiner tree problem]] again seeks a system of line segments connecting all given points, but without requiring the segments to start and end only at given points. In this problem, additional points may be added as segment endpoints, allowing the Steiner tree to be shorter than the minimum spanning tree.{{r|gilpol}}
*In the Euclidean [[Travelling salesman problem|traveling salesperson path problem]], the connecting line segments must start and end at the given points, like the spanning tree and unlike the Steiner tree; additionally, each point can touch at most two line segments, so the result forms a [[polygonal chain]]. Because of this restriction, the optimal path may be longer than the Euclidean minimum spanning tree, but is at most twice as long.{{r|shahoe}}
*[[Geometric spanner]]s are low-weight networks that, like the minimum spanning tree, connect all of the points. Unlike the minimum spanning tree, all of these connecting paths are required to be short, having length proportional to the distance between the points they connect. To achieve this property, these networks generally have cycles
==Properties==
| |||