## Abstract

We studied the Steiner tree problem in four uniform orientations where any line, half-line, or line segment must be on a line which makes an angle of (iπ)/4 with the positive x-axis, for some i ∈ {0,1,2,3}, and the distance between two points is measured as the length of the shortest polygonal path connecting them. We show that for any set P of n terminal points there exists a Steiner minimum tree interconnecting P such that all Steiner points are in script G sign^{[2n/3]-1}(P), the ([(2n)/3] - 1)^{sl}-generation grid points of P. Our result improves the previous best result which guarantees that for any set P of n terminal points there is a Steiner minimum tree in which all Steiner points are in script G sign^{n-2}(P).

Original language | English (US) |
---|---|

Pages (from-to) | 287-301 |

Number of pages | 15 |

Journal | Networks |

Volume | 35 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2000 |

Externally published | Yes |

## Keywords

- Octagonal routing
- Steiner minimum trees
- Uniform orientations
- Vlsi design

## ASJC Scopus subject areas

- Software
- Information Systems
- Hardware and Architecture
- Computer Networks and Communications