Full Steiner trees for the obstacle-avoiding rectilinear Steiner tree problem – Københavns Universitet

Full Steiner trees for the obstacle-avoiding rectilinear Steiner tree problem

Master thesis defence by Daniel Dahl Juhl

Abstract:

The GeoSteiner approach is a well-known method for solving the geometric Steiner tree problems. In this thesis, I investigate the possibility of generalizing the GeoSteiner approach to solve the obstacle-avoiding rectilinear Steiner tree problem by examining the properties of full Steiner trees among obstacles. I explain two different schemes for handling the presence of obstacles by the introduction of virtual terminals, as suggested in the 2013 ObSteiner paper of Huang and Young. The main contribution of this thesis is a new, self-contained proof of the fact that full Steiner trees among obstacles must conform to one of four Hwang-like topologies if the virtual terminals are placed after a certain scheme. I also discuss how a full Steiner tree generation algorithm based on this result could be implemented in practice, which involves generalizing upper bounds and empty region properties used in the GeoSteiner approach to the obstacle-avoiding case. Finally, I empirically investigate the differences and similarities between the full Steiner trees generated using Huang et. al.'s ObSteiner approach and the ones generated for obstacle-less problems by GeoSteiner.

Censor: David Pisinger, DTU

Supervisor: Martin Zachariasen, DIKU