Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909524373274624 |
|---|---|
| author | Yang, Puhan Li, Guchan |
| author_facet | Yang, Puhan Li, Guchan |
| contents | The rectilinear Steiner minimum tree (RSMT) problem computes the shortest network connecting a given set of points using only horizontal and vertical lines, possibly adding extra points (Steiner points) to minimize the total length. RSMT solvers seek to balance speed and accuracy. In this work, we design a framework to boost existing RSMT solvers, extending the Pareto front. Combined with GeoSteiner, our algorithm reaches 5.16\% length error on nets with 1000 pins. The average time needed is 0.46 seconds. This provides an effective way to solve large-scale RSMT problems with small-scale solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02319 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy Yang, Puhan Li, Guchan Data Structures and Algorithms Computational Geometry Discrete Mathematics The rectilinear Steiner minimum tree (RSMT) problem computes the shortest network connecting a given set of points using only horizontal and vertical lines, possibly adding extra points (Steiner points) to minimize the total length. RSMT solvers seek to balance speed and accuracy. In this work, we design a framework to boost existing RSMT solvers, extending the Pareto front. Combined with GeoSteiner, our algorithm reaches 5.16\% length error on nets with 1000 pins. The average time needed is 0.46 seconds. This provides an effective way to solve large-scale RSMT problems with small-scale solvers. |
| title | Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy |
| topic | Data Structures and Algorithms Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2503.02319 |