Preprocessing obstacles for Steiner tree problems in Minkowski planes
by Marcus Gordon Volz
Abstract: The obstacle-avoiding Steiner tree problem asks for a shortest embedded network spanning a given set of points such that no part of the network intersects the interiors of a given set of obstacles. The efficiency of exact algorithms for constructing minimum obstacle-avoiding Steiner trees can be improved by reducing the number of vertices and edges that need to be considered for the given obstacles. In this talk we introduce new methods for simplifying the geometry of obstacles for Steiner tree problems in Minkowski planes, and demonstrate their effectiveness by performing experimental results on randomly-generated obstacles in different metrics.
For More Information: Contact: Sanming Zhou. email: email@example.com