Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
By: Puhan Yang, Guchan Li
Potential Business Impact:
Finds shortest paths for computer chips faster.
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.
Similar Papers
Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
Computational Geometry
Finds better ways to connect points on a curved surface.
An RRT* algorithm based on Riemannian metric model for optimal path planning
Robotics
Helps robots find the best path in tricky places.
Search Trees on Trees via LP
Data Structures and Algorithms
Finds best ways to search through tree-like data.