✦ LIBER ✦
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
✍ Scribed by Brazil, M.; Thomas, D. A.; Weng, J. F.
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 168 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectilinear Steiner problem for the case where terminals are constrained to lie on almost any fixed set of simple disjoint compact curves.