Rectilinear Trees Under Rotation and Related Problems: Extended Abstract

B. K. Nielsen, P. Winter, Martin Tvede Zachariasen

Research output: Contribution to conferenceAbstract

Abstract

We consider the problem of nding a minimum spanning tree for a set of points in the plane where the orientations of edges are restricted to uniformly distributed orientations, = 2; 3; 4; : : :, and where the coordinate system can be rotated around the origo by an arbitrary angle. The most important case with applications in VLSI design arises when = 2; in this, so-called rectilinear case, the edges have to be parallel with the x- or y-axis. We suggest a straightforward algorithm to solve this problem. We also discuss how to solve the rectilinear Steiner tree problem in the rotational setting. Finally, we provide some computational results indicating the average savings for dierent values of n and both for spanning and Steiner trees.
Original languageEnglish
Pages1-5
Number of pages5
Publication statusPublished - 2002

Fingerprint

Dive into the research topics of 'Rectilinear Trees Under Rotation and Related Problems: Extended Abstract'. Together they form a unique fingerprint.

Cite this